A switch network (the name is invented) is made with three types of nodes:one Start nodeone End nodeone or more Switch nodesThe switch node has 3 exits: Left, Up, Right; has two states L and R anda target state TL or TR. Each switch can be traversed with the following rules:always from Left to Up; the state of the switch changes to Lalways from Right to Up; the state fo the switch changes to Rfrom Up to Left only if the switch is in state L; the state doesn't changefrom Up to Right if the switch is in state R; the state doesn't changenever from Left to Right or Right to LeftFigure 1. Switch node in state L with target state TRThese properties also hold:0, 1 or 2 of the exits of a switch can be isolated (not connected to another switch);a path can just touch a switch to change its state: enter from Left and exit from Left or enter from Right and exit from Right; there are no restrictions on the number of times a switch can be traversed / touched.The decision problem is: Does a path from the Start node to the End nodeexist such that all the final states of the switches match the corresponding target state?Obviously, all the switches that are not initially in their target state must be traversed (or touched) at least once;This is a quick draw of a trivial network (made with Excel ... I'll make a better one):A trivial solutions is:S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> EEDIT 2:Is this problem known? ---> you gave me the good reference to the Hearn's thesis (constraint graphs);The problem is in $NPSPACE = PSPACE$; before posting a sketch of my proof that it is in NP, I found an error; so the open questions are again:2 . Is it $\mathsf{NP}$?3 . Has the problem any chance to be $\mathsf{NP\text{-}complete}$?
Complexity of a switch network problem
ds.algorithms;reference request;graph algorithms;np