Consider an oriented graph (multi-graph). Assume some set of vertices is marked 'Init1','Init2','Init3'... and another set of vertices is marked by 'Final1','Final2',...

I am interested in the "efficient" algorithms which will determine is it possible to "MOVE" markers "InitNN" to positions 'FinalNN'. Where we allowed to "MOVE" marker from a vertex to an outgoing edge and from incoming edge to corresponding vertex. With the CONSTRAINT that two markers are NOT allowed to be at the same place.

Question There can be many approaches to solve the problem, I am interested in analysis their complexity. Any ideas are welcome. For example if graph is "random" in certain sense what can be the algorithm the least average complexity ?

Where complexity is counted in number of operations (write a C-code, compile to and calculate the number of cycles - this is well-defined complexity measure, different compilers and CPU will give approximately same result).

Example of algorithm It seems the simplest way to solve a problem is the following. Essentially it can be reduced to determining where two vertices are connected in some bigger graph, which in turn can be solved by "wave algorithm". I mean let us enumerate all possible marker configurations - it will give vertices of the "new graph". Let us connect two vertices (configurations) if there is a "MOVE" which goes form one to another. By "wave algorithm" (it is Russian name I am not sure in English translation) I mean the following - take an initial vertex and find all connected to it; next step find all vertices connected to vertices found on the previous step; and so on....

Question What about efficiency of this algorithm ? Can one propose better ?