11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think you're right about "at most 4 paths connecting any pair". See: i.imgur.com/mYL4n1V.png $\endgroup$ – svinja May 20 '13 at 15:47
  • 1
    $\begingroup$ @svinja You are right, I should have said at most 4 pairwise edge disjoint paths exist between any pair of two vertices. $\endgroup$ – Listing May 20 '13 at 15:53
  • $\begingroup$ Your title is misleading, because the longest simple cycle can be none of the two cycles in the decomposition of $E$ (in any decomposition). $\endgroup$ – Denis May 22 '13 at 12:00
  • $\begingroup$ @dkuper it can actually, look at the union of two vertex disjoint simple cycles. $\endgroup$ – Listing May 22 '13 at 12:01
  • $\begingroup$ My point is not that it can never be one of them, it is that sometimes it is not one of them. So the problem is not finding the bigger of the two. $\endgroup$ – Denis May 22 '13 at 12:43
2
+50
$\begingroup$

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$)

enter image description here

The larger picture can be downloaded here

$\endgroup$
  • $\begingroup$ This is a very beautiful proof, maybe you should direct the edges in figure 'A' to make it easier to understand how to get the paths (I think I understood it though). $\endgroup$ – Listing May 25 '13 at 15:31
  • $\begingroup$ @Listing: the construction of the paths doesn't depend on the directed edges (indeed I wrote "undirected" search in the answer). You should start from an arbitrary node, make a depth first scan from it coloring with red the edges traversed, then backtrack to the first degree 3 node encountered and continue the depth first scan from it coloring with green the edges traversed, and so on ... perhaps it has a more formal definition, but it doesn't come to my mind now. Let me know if you need further details. $\endgroup$ – Vor May 25 '13 at 18:22
  • $\begingroup$ I see, the property that edges are traversed in the 'correct' direction is enforced by the last transformation. Thank you for the clarification. $\endgroup$ – Listing May 25 '13 at 18:41
0
$\begingroup$

Inspired by Vor's answer, I want to give a simpler one.

Start with Hamiltonian cycle problem for grid graphs problem which was proven hard by Itai.

It can be easily seen that edge set of a grid graph can be partitioned into 2 disjoint subsets: horizontal and vertical.

So now, we need to weave all horizontal ones into one simple cycle, and weave all vertical ones into another simple cycle.

This is very easy task: for vertical ones, sweep from leftmost to rightmost, just connect any vertical gaps, then connect consecutive x-coordinated vertical line, then connect the lowest leftmost vertex with the highest rightmost vertex. Do similarly for horizontal edges.

Note that the obtained graph is still simple, undirected and satisfies requirement. It is simple because at the last steps of vertical phase and horizontal phase, we deal with two different vertex pairs.

Now, do a similar trick as Vor did. At each vertex, for each of its original incident edge, add $k$ new vertices. As usual, $k$ ahouls be large enough. Lastly, the length of a genuine Hamiltonian cycle should be $2k|V|$. But of course, it is not hamiltonian of the obtained graph.

$\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.