The question is close to the [Sokoban][1] game (thanks to Dima Pasechnik !), but a little different in details.
 
Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, chipe2,..., chipM). Put chips on some set of vertices 'Init1','Init2','Init3'...
And consider some other set of  vertices 'Final1','Final2',..., 'FinalM'.

**Question** Propose an "efficient" algorithm which will determine is it possible to "MOVE" chips from positions "InitNN" to positions 'FinalNN'.


Where we are allowed to "MOVE" chip from a vertex to an outgoing edge and from incoming edge to corresponding vertex.
With the CONSTRAINT that two chips are NOT allowed to be at the same place.
One move - moves  only ONE chip.
ChipK should go to position FinalK - same "K".


**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 (I actually wrote a Matlab 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 "breadth-first search" ("wave algorithm" in Russian) (I mean let us enumerate all
possible chip 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 "breadth-first search"  ("wave algorithm" in Russian) 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 ?


  [1]: http://en.wikipedia.org/wiki/Sokoban