Prof. Meirav Zehavi

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).