We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle is required, not the actual cycle. Thanks a lot in advance for any ideas and suggestions.
Longest cycle containing two nodes
-
0I think the question(s) are still relevant. I had a hard time finding the resources for the answer, so actually I think it is nice that this question changed a couple of times. I can always change my answer to make it more fit for 3 questions. – 2012-04-22
1 Answers
Edit: The original question was for undirected graphs.
The problem is NP-Complete. Assume that given an undirected graph $G$, and two vertices $a$ and $b$, you can find two vertex-disjoint paths $P_1$ and $P_2$ from $a$ to $b$ such that the length of $P_1$ plus the length of $P_2$ is as large as possible. Then you can solve the hamilton tour problem.
Take an undirected graph $G$, and pick two vertices, $a,b$ in $G$. Now find two vertex-disjoint paths $P_1,P_2$ such that the sum of their lengths is maximum. Now look at the cycle $C$ consisting of both paths merged together in $a$ and $b$.
If $C$ includes all vertices in $G$, then $C$ is a hamiltonian cycle. If $C$ does not use all vertices in $G$, then there is no hamiltonian cycle in $G$, since such a cycle would yield two paths with larger total length.
For the directed case: As stated in Complete of Disjoint Paths Problems in Planar Graphs, the article The directed subgraph homeomorphism problem shows that it is NP-hard to determine if a directed graph has 2 vertex disjoint paths from $a$ to $b$ and from $c$ to $d$.
Since the decision problem is hard, so is the optimization version.
For the cycle-version Given a directed graph $G$, we want to find the longest directed cycle containing two vertices $a$ and $b$ in $G$. If we can find such a maximum cycle, we are able to determine if $G$ is hamiltonian by looking at the size of the cycle.
Since the problem of determining whether a directed graph has a hamiltonian cycle is NP-Complete, so is this problem.
-
1Add the new question as an appendage to the original question, in that way, the answer i posted is still useful in the future. – 2012-04-21