Why does longest simple path lack optimal substructure when shortest path has it?

## The two problems look symmetric and are not Swapping `min` for `max` in a shortest-path recurrence feels like it should give longest paths. It does not, and the reason is the textbook illustration of why optimal substructure must be *argued* rather than assumed. First, the definitions matter. A **simple path** visits no town twice. Without that restriction, "longest path" is meaningless in any graph containing a cycle — you would loop forever. The restriction is what makes the question well posed, and it is also exactly what destroys the property. ## A concrete road map Four towns, five one-unit roads: ``` A - B roads: A-B, B-C, C-D, D-A, B-D | \ | D - C ``` Adjacency: `A: B, D` — `B: A, C, D` — `C: B, D` — `D: A, C, B`. **Failure one — the optimal whole does not contain optimal parts.** The longest simple route from A to C is `A-B-D-C`, three roads (or the mirror `A-D-B-C`). Cut it at B. Its prefix is the single road `A-B`, length one. But the longest simple route from A to B is `A-D-C-B`, length three. So the optimal solution to the whole problem contains a *sub-optimal* solution to the subproblem. The cut-and-paste argument that carries shortest paths cannot even get started here. **Failure two — the pieces are not independent.** Try to build the answer anyway: take the longest simple A-to-B route, `A-D-C-B`, and the longest simple B-to-C route, `B-A-D-C`, and concatenate at B. The result visits A, D and C twice each. It is not a simple path; it is not a valid solution at all. Pasting optimal pieces produced something outside the solution space. That second failure is the deeper one. The constraint "no repeated town" is **global**: it is a property of the whole route, not of either half separately. Whichever towns one half consumes are forbidden to the other. Two subproblems that compete over a shared resource — here, the pool of unvisited towns — are not independent, and independence is precisely the condition the exchange argument relies on. ## Why shortest paths escape both failures For shortest paths with non-negative edge costs, cut an optimal A-to-Z route at any town M. If the A-to-M portion were not shortest, substitute a shorter one and the total drops — contradiction. The substitution is always legal because the suffix does not care how you reached M; there is no constraint linking the halves. (A shortest route also never repeats a town when costs are non-negative, so simplicity comes for free rather than being an extra constraint you must enforce.) The asymmetry is therefore not about minimising versus maximising. Plenty of maximisation problems have flawless optimal substructure. It is about whether the subproblems are independent, and about whether the constraint defining a valid solution is local or global. ## The consequence, and the honest thing to say Because the property fails, no straightforward recurrence over (current town, destination) is sound. Finding a longest simple path in a general graph is NP-hard, so no polynomial-time algorithm is known for it — which is a much stronger statement than "my recurrence did not work." Two tempting repairs and why they fail: - **Negate the road lengths and run a shortest-path search.** Negative edge costs make cycles with negative total length possible, and then "shortest" is unbounded — the search is ill-posed rather than merely slow. Negation converts a hard problem into an ill-defined one, not an easy one. - **Restore independence by widening the state.** This is the principled fix and it genuinely works: make the subproblem `(current town, set of towns already visited)`. The pieces become independent again because the shared resource is now part of the key. The catch is that the state space grows with the number of subsets of towns, which is exponential — correct, but not polynomial. Widening state to restore independence always costs state-space size; here the cost is prohibitive. ## What an interviewer is listening for A weak answer says "longest path just doesn't work with DP." A strong one distinguishes the two failures — sub-optimal pieces inside the optimal whole, and pieces that cannot legally be pasted — names the global simplicity constraint as the coupling, and volunteers the state-widening repair together with its exponential price. Being able to produce a four-town counterexample on demand is what makes the answer credible rather than recited.