6
$\begingroup$

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).

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$ Feb 27, 2012 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.