Page 301 ebook, DP chapter

#1

It says in the common mistakes when applying DP section:
If the longest path without repeated cities from city 1 to 2 pass through city 3, then the subpaths from 1 to 2 and from 2 to 3 may not be the longest paths without repeated cities.

What does it mean? Is this typo or correct?
If the path from c1 to c2 that is the longest passes thru c3, the subpath it uses for c1 to c3 is the longest path from c1 to c3 by definition. If there were any other subpath from c1 to c3 that was longer, that subpath would have been included in the longest path from c1 to c2.

0 Likes

#2

It is a little subtle here. I think an good example is that the longest path from c1 to c3 is actually c1->c2->c3. So that is one reason the subpath may not be the longest path between them.

Many people fall into different traps while solving the longest path problem, for example, use negative weight on edge and try to reduce this to shortest path problem.

0 Likes

#3

Yes, I got it.

That explanation makes sense.

The operative phrase in the sentence is “without repeated cities” which is what makes the solution to the longest path problem not individually be the solution to the subproblems/subpaths. In essence, if the solution to the longest path “without repeated cities” between C1 and C2 passes thru C3, then there could potentially be a different absolute longest path between C1 and C2 but one which has repeated cities. Anytime there is any overlap of cities in the solutions for the two subpath problems (C1 to C3, and C3 to C2), those two subpaths can’t individually combine to produce the longest path solution without repeated cities for C1 to C2.

Had the problem been of simply finding the longest path between C1 and C2 (with or without repeated cities), then the solution to it would yield solution to the subproblems too.

0 Likes