<p>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.</p>

<p>See also <a href="https://cstheory.stackexchange.com/questions/2396/counting-the-number-of-hamiltonian-cycles-in-cubic-hamiltonian-graphs">this question</a> and <a href="https://cstheory.stackexchange.com/questions/1651/hamiltonicity-of-k-regular-graphs">this one</a>.</p>

CC BY-SA 3.0
2012-02-27T08:54:02.630Z
@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
CC BY-SA 3.0
2012-02-27T07:48:39.137Z
2012-02-27T07:48:39.137Z
2017-04-13T12:32:28.743Z
Jeffε
<p>Working on a problem I came up with the following "T-gadget":
<img src="https://i.sstatic.net/j25dV.jpg" alt="enter image description here"></p>

<p>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.</p>

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

<ol>
<li>go back through wire A2, OR</li>
<li>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</li>
</ol>

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

<pre><code>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)
</code></pre>

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

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

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

<cc.complexity-theory><np-hardness>
NP-completeness of a problem using a "T-gadget"
Marzio De Biasi
# NP-completeness of a problem using a "T-gadget"

(Asked by: username_0 on 2012-02-26)

Working on a problem I came up with the following "T-gadget":

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:

go back through wire A2, OR
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).

**Tags:** cc.complexity-theory, np-hardness


---

## 1 answers

### Answer by username_1 on 2012-02-27. Score: 8 | Accepted answer

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](https://cstheory.stackexchange.com/questions/2396/counting-the-number-of-hamiltonian-cycles-in-cubic-hamiltonian-graphs) and [this one](https://cstheory.stackexchange.com/questions/1651/hamiltonicity-of-k-regular-graphs).

> **Comments:**
> **username_0**: @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.  

---

