1
$\begingroup$

I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ?

1) Graph is undirected , and every node has degree two.

Any help will be appreciated. Thanks.

$\endgroup$
1
$\begingroup$

If every node has degree two, then the test for a Hamiltonian cycle boils down to testing connectivity, since the graph must then consist of 0 or more disconnected cycles.

The algorithm is as follows:

Choose a starting node v
marked[v] = true
x := v
while x has an unmarked neighbour u
    x := u
    marked[u] = true
if all nodes in the graph are marked, return true, else return false

Suppose we see $v_1 \cdots v_n$ in this process. Since each node has degree 2, we only stop when we see a node with both its neighbors marked, so $v_1 \cdots v_n$ is a cycle in the graph. Since we see two edges from each $v_i$, there can be no other nodes connected to any $v_i$ that are unmarked. Thus, either $v_1 \cdots v_n$ is all nodes in the graph, and there is a cycle, or there is another connected component, and there is not a cycle.

Clearly this test is linear time, so the problem is in $P$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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