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 ?