4
$\begingroup$

Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem I'm trying to solve is given a list of words, find the longest chain of words such that the last letter of the $n^{th}$ word in the chain is the same as the first letter of the $n+1^{th}$ word in the chain. So the number of vertices would be 26 (the length of the alphabet), and each edge would represent the words that start with the letter which its from vertex corresponds to and ends with the letter which its to vertex corresponds to. The list is about 60,000 words long, so something like $O(cV)$ or $O(cV^2)$ where $c$ is the total capacity would be nice.

$\endgroup$
2
$\begingroup$

In general, for a general graph with an arbitrary number of vertices, no. The general problem is NP-hard (consider the case where all edge capacities are 1; this is the longest trail problem, which is NP-hard; my thanks to Willard Zhan for pointing out the connection to the longest trail problem),. Therefore, there is unlikely to be an algorithm that is always correct and is efficient for all graphs.

In your case, it might be possible, as you can represent your problem as a graph with 26 vertices (one per letter) and 60,000 edges (one per word). Moreover, you can condense it to a graph with 26 vertices (one per letter) and $26^2$ edges (one per pair of vertices). Then, an exponential-time algorithm might suffice. I don't know of any such algorithm, but I also can't rule out the possibility, either.

How to condense the graph? Take all of the words (edges) that start with letter $i$ and end with letter $j$, sum up their corresponding capacities, and then add a new edge $(i,j)$ whose capacity is equal to that sum. That leaves you with a single edge per pair of letters. Any path through such a graph that respects the summed capacities can be transformed into a path in the original graph that respects the original capacities.

I realize this doesn't solve your problem, but maybe it is a small step towards that goal.

$\endgroup$
5
  • $\begingroup$ And, in general, any time somebody says, "I have this problem where I need to find the longest path such that...", your first reaction should be to blurt out "That's NP-hard." You won't be wrong very often. $\endgroup$ – David Richerby Jul 31 '18 at 17:55
  • 1
    $\begingroup$ If you use 26 vertices for each letter of the alphabet, you could pass through vertices multiple (or zero) times, so I don't see how it would necessarily be equivalent to finding a Hamiltonian path. Is it possible that there could be an algorithm that doesn't take exponential time? $\endgroup$ – pommicket Jul 31 '18 at 18:10
  • 2
    $\begingroup$ When edge capacities are 1, it is not the Hamiltonian path problem, but the longest trail problem. $\endgroup$ – Willard Zhan Jul 31 '18 at 18:36
  • $\begingroup$ @WillardZhan, good point. Thanks for the correction! $\endgroup$ – D.W. Jul 31 '18 at 20:19
  • $\begingroup$ @LeoTenenbaum, you're right. See updated answer. $\endgroup$ – D.W. Jul 31 '18 at 20:19

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.