Four shortest vertex-disjoint paths in planar graphs

With Yipu Wang*.

Preprint, October 2017.

Let G be an edge-weighted planar graph with 2k terminal vertices s1, t1, ..., sk, tk. The minimum-sum vertex-disjoint paths problem asks for a set of pairwise vertex-disjoint simple paths of minimum total length, where the ith path connects si to ti. Even when all terminals lie on a single face, efficient algorithms for this problem are known only for fixed k≤3. We describe the first polynomial-time algorithm for the case of four arbitrary terminal pairs on a single face.

Publications - Jeff Erickson ( 05 Apr 2018