6

Working on a problem I came up with the following "T-gadget": enter image description here

It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2); it can be rotated (0, 90, 180, 270 degrees); two gadgets X and Y, can be linked together (one connector of X is joined with one connector of Y); the wires used to link the T-gadgets cannot overlap.

A signal is propagated on the wires; and it can use 1 or 2 connectors to traverse a T-gadget. Suppose that it enters through wire A1, then it can:

  1. go back through wire A2, OR
  2. choose among connector B or C - suppose that it chooses connector B; then it can exit the gadget through wire B1, re-enter through B2 and exit again through A2

When a signal enters a gadget and exits from the same connector, the gadget is "activated".

Possible traversals of a T-gadget:
(OUT) - A1 - A2 (OUT)
(OUT) - A1 - B1 - (OUT) - B2 - A2 - (OUT)
(OUT) - A1 - C1 - (OUT) - C2 - A2 - (OUT)
(OUT) - B1 - B2 (OUT)
(OUT) - B1 - A1 - (OUT) - A2 - B2 - (OUT)
(OUT) - B1 - C1 - (OUT) - C2 - B2 - (OUT)
(OUT) - C1 - C2 (OUT)
(OUT) - C1 - B1 - (OUT) - B2 - C2 - (OUT)
(OUT) - C1 - A1 - (OUT) - A2 - C2 - (OUT)

The signal starts on wire A1 of a gadget (with connector A unlinked) and must return to A2.

Question: is the problem: "Given a set of T-gadgets linked together, does exist a path that activates all of them?" $NP$-complete?

If we omit option 1 (go back through wire A2) I think that the problem is $NP$-complete (through reduction from Hamiltonian path problem on cubic planar graphs).

Community
  • 1
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127

1 Answers1

8

You're asking whether the underlying 3-regular graph has a Hamiltonian path, which is NP-complete. Your activation signal must traverse every edge in this path exactly twice.

See also this question and this one.

Community
  • 1
Jeffε
  • 23,129
  • 10
  • 96
  • 163
  • @jeffe: now I see that option 1 go back through wire A2 (without going further) does not alter the problem: it can (must) be used only at the end of the Hamiltonian path on the underlying cubic planar graph. Thank you! ... I'll wait a bit to see if other tiny variations (of the question) come up, otherwise I'll accept your answer. – Marzio De Biasi Feb 27 '12 at 08:54