Min-sum two edge-disjoint paths

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected graph and let $(s_1,t_1)$ and $(s_2,t_2)$ be specified vertex pairs. A path is simple and has length equal to its number of edges. Seek paths $P_1,P_2$ satisfying \[ P_i:s_i\leadsto t_i\quad(i=1,2),\qquad E(P_1)\cap E(P_2)=\varnothing, \] whose total length $|E(P_1)|+|E(P_2)|$ is minimum.

The source asks for a combinatorial polynomial-time algorithm that finds an optimum pair or reports that no feasible pair exists. Its discussion already records randomized algebraic polynomial-time methods; the desired conclusion is a deterministic combinatorial method for the exact optimum. One can focus on four distinct terminals; coinciding-terminal cases have the same explicit path convention.

Paths may share intermediate vertices: only their edge sets must be disjoint. Their prescribed pairings cannot be exchanged. The objective is the minimum sum, so neither path need be individually shortest in the original graph; accepting a longer first path may permit a much shorter second path. Finding two feasible disjoint paths, or deciding whether two individually shortest paths can be disjoint, does not solve the optimization problem. All edges in this formulation have unit length; no ambiguity about arbitrary real input weights is needed for the original unweighted target.

Short English statement

Find a deterministic combinatorial polynomial-time method for two edge-disjoint paths with prescribed pairings and minimum total length.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000055 (AMR-029-0055), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Min-sum two edge-disjoint paths. Original source indexed by AMR-029-0055. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Min-sum two edge-disjoint paths. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Min-sum_two_edge-disjoint_paths.