Input: $k in mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a part of the input). Question: Is there a simple cycle in $G$ with length greater than $k$?
Obviously the problem is in NP and the maximum degree in $G$ is $leq 4$, but that doesn’t seem to help.
Asked By : Listing
Answered By : Vor
- ignore the direction of the edges, and using a first depth (undirected) scan from an arbitrary node, divide the edges of $G$ in two sets of distinct (undirected) paths (red and green in the figures);
- join the red paths adding extra “linking nodes” (purple nodes in the figure B) and make an undirected red circuit; join the green paths adding extra “linking nodes” (purple nodes in the figure) and make an undirected green circuit;
- transform each original node $b in V$ of indegree 1 and outdegree 2 (figure C), adding $k$ yellow nodes on the inbound red edge $ato b$, and adding $k$ yellow nodes on the first outbound red edge $b to c$; finally add $k$ yellow nodes “towards” the second outbound green edge $b to d$ using a “wrapped” path around $b$ that touches the outermost yellow nodes of the red edges (figure D).
In the resulting graph all the $3k$ yellow nodes can be traversed by a simple path only in the two ways showed in figure E and figure F, which correspond to the two valid traversals of the original node $b in V$; informally if an edge towards the extra “linking” purple node is used, $k$ yellow nodes cannot be traversed.
- transform each original node of V of indegree 2 and outdegree 1 in a similar way
Picking a large enough $k gg |V| $, the result graph $G’$ has an simple path of length greater than $3k(|V|-1)$ if and only if the original graph $G$ has an Hamiltonian path (of length $|V|-1$) 
The larger picture can be downloaded here
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12148
