Min-Sum disjoint paths on subclasses of chordal graphs

• Polynomial-time algorithm solving Disjoint Shortest Paths on split graphs. • FPT algorithm solving Min-Sum Disjoint Paths on split graphs. • Polynomial-time algorithm solving DSP on well-partitioned chordal graphs. • FPT algorithm solving Min-Sum DP on well-partitioned chordal graphs. • Linear-time algorithm solving Min-Sum DP on threshold graphs. We study the optimization version of the classic Disjoint Paths problem, known as Min-Sum Disjoint Paths , as well as its restriction to shortest paths, known as Disjoint Shortest Paths . Both problems are notoriously hard in the sense that very few positive results are known in their context even when confined to grids, in contrast to the classic Disjoint Paths problem, despite significant research efforts in recent years. In light of this, we focus on restricted graph classes, being subclasses of chordal graphs: specifically, we consider the classes of split graphs, well-partitioned chordal graphs, and threshold graphs. For each of the two problems and each of these graph classes, we provide either a polynomial-time algorithm or a fixed-parameter algorithm (when a polynomial-time algorithm is unlikely to exist).