[Solved]: Longest cycle contained in two cycles

Problem Detail: 

Is the following problem NP-complete? (I assume yes).

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

A reduction attempt ....

Reduction from Hamiltonian path on digraph $G = (V,E)$ with max degree 3 which is NPC [G&J]

• 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 $a\to 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