Hamiltonian circuit in at least one component

262 Views Asked by At

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit.

Intuitively it's clear - Hamiltonian circuit in one graph is NP-complete, and this problem can be thought of as "Hamiltonian circuit in at least one of several graphs", so an algorithm could check each graph for a circuit and return "yes" if at least one contains the circuit.

But, from an admittedly meticulous point of view, a reduction should be shown from one graph $A$ to graph $B$, s.t. graph $A$ has a Hamiltonian circuit iff graph $B$ has a component with a Hamiltonian circuit.

I believe that such a reduction would be near-trivial... What am I missing? Thanks :)

1

There are 1 best solutions below

6
On BEST ANSWER

OK, so this a brave attempt at answering my own question:

Upon a graph $G$ (an input for Hamiltonian circuit), the reduction will check if $G$ has more than one connected components, and if so, will output a graph with only two vertices and one edge, i.e. with no Hamiltonian circuits anywhere. If $G$ has only one connected component, the reduction will output $G$.

The reduction takes polynomial time since finding the number of connected components takes polynomial time, and outputting the graphs clearly takes polynomial time.

Now, $G$ can contain a Hamiltonian circuit only if it has one connected component. So, $G$ has a Hamiltonian circuit <=> $G$ has a Hamiltonian circuit and only one connected component <=> the reduction outputted $G$.