# Longest cycle containing two nodes

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.

-
Hi John, I received your moderator flag. I just wanted to point out that this question and its answer below may still be useful to others on the internet, and so in general I don't like to delete questions. However, if you think that the question is so invalid as to not possibly be of use to others, then I'd be happy to delete it. – Zev Chonoles Apr 22 '12 at 1:49
I 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. – utdiscant Apr 22 '12 at 8:57

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.

-
I guess my reduction from the original problem is wrong then, thanks a lot! – John Carter Apr 21 '12 at 19:40
I know why my reduction went wrong, the graph should be directed :) I can't be sorry enough, I'm an idiot for missing so many stuff. – John Carter Apr 21 '12 at 20:08
It's almost a different question now :-/ I am sincerely sorry for the inconvenience. – John Carter Apr 21 '12 at 20:11
Add the new question as an appendage to the original question, in that way, the answer i posted is still useful in the future. – utdiscant Apr 21 '12 at 20:58