MHB Is HSC NP-Complete in Graph Theory?

[mathmari]

Hey!

I am looking at the following solved exercise:
A cycle $C$ in a graph is called simple, if no vertex in $C$ is appeared more than twice. For example a hamiltonian cycle is a simple cycle, that goes through every vertex of a graph.
The HALF-SIMPLE-CYCLE (HSC) Problem asks if in a graph with $n$ vertices there is a simple cycle of length $\geq \frac{n}{2}$.
Show that HSC is NP-complete. The solution is the following:
Let $G=(V,E)$ a graph with $V=\{1, \dots, n\}$. We add to $G$ $n$ vertices, but no other edges. That means that we define $V'=\{1, \dots , 2n\}$ and $G'=(V',E)$. Then it holds that $G\in \text{ HAM } \Leftrightarrow G'\in \text{ HSC }$. First of all, to show that the problem is NP-complete, we have to show that it is NP and that it is NP-hard, right? (Wondering)

To show that the problem is in NP, we do the following:
A non-deterministic Turing machine guesses a cycle of length $\geq \frac{n}{2}$ and checks if this cycle is simple. This takes linear time, which is equal to the size of the cycle.
Is this correct? (Wondering)

Then to show that the problem is NP-hard, we want to reduce the HAM Problem to the HSC Problem.
The HAM Problem is to determine if there is a simple path that crosses each vertex of the graph.
When we consider for the HSC Problem a graph $G'$ that is created by $G$ when we add $n$ more vertices, without edges, we have the following:
When $G$ is in HAM, we know that there is a simple path that crosses each vertex of the graph. That means that for $G'$ there is a simple path that crosses the half number of all vertices of the graph, so $G'$ is in HSC.
Is this correct? (Wondering)
Is this an iff statement, or do we have to prove also the other direction? (Wondering)

 

[Evgeny.Makarov]

A cycle $C$ in a graph is called simple, if no vertex in $C$ is appeared more than twice.

I am bothered by this definition. So, if $a,b,c\dots$ are vertices, is the following cycle simple: $a,b,c,d,b,e,a$ (provided adjacent vertices in this sequence are connected)? Wikipedia defines a simple cycle as a "closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex".

First of all, to show that the problem is NP-complete, we have to show that it is NP and that it is NP-hard, right?

Yes.

To show that the problem is in NP, we do the following:
A non-deterministic Turing machine guesses a cycle of length $\geq \frac{n}{2}$ and checks if this cycle is simple. This takes linear time, which is equal to the size of the cycle.
Is this correct?

Yes, though I am not sure about linear time. The Turing machine model of computation is robust only with respect to polynomial time, meaning that this concept does not depend on the implementation details of the machine (whether the tape is infinite in both directions and so on). Within polytime, computations that take linear time on a two-tape machine generally take quadratic time on a single-tape machine. So if we insist on linear time, it may be necessary to define a TM more precisely.

Then to show that the problem is NP-hard, we want to reduce the HAM Problem to the HSC Problem.

Yes.

The HAM Problem is to determine if there is a simple path that crosses each vertex of the graph.

This is not precise enough. The key is visiting each vertex (except for the first and last one) exactly once.

When $G$ is in HAM, we know that there is a simple path that crosses each vertex of the graph. That means that for $G'$ there is a simple path that crosses the half number of all vertices of the graph, so $G'$ is in HSC.
Is this correct?

Yes.

Is this an iff statement, or do we have to prove also the other direction?

The answer is yes to both questions.