Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.