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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.