patternMinor
Longest path with limited edge traversals
Viewed 0 times
pathwithtraversalsedgelimitedlongest
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#95825, answer score: 2
Revisions (0)
No revisions yet.