patternModerate
What is the intuition on why the longest path problem does not have optimal substructure?
Viewed 0 times
problemwhythepathoptimalwhathavesubstructuredoeslongest
Problem
I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think the statement needs to be corrected to longest simple paths on general graphs is not solvable by dynamic programming).
If we assume they have to be simple (for some reason this is required which I don't appreciate yet) and longest, then its easy to create a counter example. Consider the square graph with 4 nodes A→B→C→D→A.
A longest path from A to D is clearly A→B→C-D. But the longest path from B to C is not part of the longest path to from A to D because the longest path from B to C is B→A→D→C which is clearly not the same as the path B→C (which in this case is in fact a shortest path!).
This seems to work only because we required the paths to be simple. Is it necessary to assume that the paths must be simple for us to prove that optimal substructure is not present?
I think that the counter example should be good evidence/proof (which I don't deny), I just don't find the counter example very enlightening at all. I see why it proves the point that it doesn't allow optimal substructure but it fails to provide me real understanding or intuition why it should be obvious that there should be no longest path optimal substructure. Like for example, why doesn't a cut and paste argument work? If the subpath isn't longest, then just stick in a longer path! It sounds very tempting, I mean, if we put in place something longer then of course it should get longer...though, this is for some reason wrong. Does the example actually in fact prove that DP can never solve longest (simple?) paths efficiently? I don't require for a general proof that its not in P (since thats might be asking for a P vs NP solution). I am just after a proof that its not solvable by DP (or at least very strong evidence that DP can never solve this longest paths problem or that the problem does not have
If we assume they have to be simple (for some reason this is required which I don't appreciate yet) and longest, then its easy to create a counter example. Consider the square graph with 4 nodes A→B→C→D→A.
A longest path from A to D is clearly A→B→C-D. But the longest path from B to C is not part of the longest path to from A to D because the longest path from B to C is B→A→D→C which is clearly not the same as the path B→C (which in this case is in fact a shortest path!).
This seems to work only because we required the paths to be simple. Is it necessary to assume that the paths must be simple for us to prove that optimal substructure is not present?
I think that the counter example should be good evidence/proof (which I don't deny), I just don't find the counter example very enlightening at all. I see why it proves the point that it doesn't allow optimal substructure but it fails to provide me real understanding or intuition why it should be obvious that there should be no longest path optimal substructure. Like for example, why doesn't a cut and paste argument work? If the subpath isn't longest, then just stick in a longer path! It sounds very tempting, I mean, if we put in place something longer then of course it should get longer...though, this is for some reason wrong. Does the example actually in fact prove that DP can never solve longest (simple?) paths efficiently? I don't require for a general proof that its not in P (since thats might be asking for a P vs NP solution). I am just after a proof that its not solvable by DP (or at least very strong evidence that DP can never solve this longest paths problem or that the problem does not have
Solution
The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:
Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.
Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence
$$
\begin{align*}
&\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\
&\ell(t,t,A) = 0.
\end{align*}
$$
If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.
You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.
While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.
Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.
Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence
$$
\begin{align*}
&\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\
&\ell(t,t,A) = 0.
\end{align*}
$$
If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.
You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.
While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.
Context
StackExchange Computer Science Q#56756, answer score: 14
Revisions (0)
No revisions yet.