Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
@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 8:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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