Prof. Meirav Zehavi

Given an undirected graph G and a multiset of k terminal pairs X, the VERTEX-DISJOINT PATHS ([Figure presented]) and EDGE-DISJOINT PATHS ([Figure presented]) problems ask whether G has k pairwise internally vertex-disjoint paths and k pairwise edge-disjoint paths, respectively, connecting every terminal pair in X. In this paper, we study the kernelization complexity of [Figure presented] and [Figure presented] on subclasses of chordal graphs. For [Figure presented], we design a 4k vertex kernel on split graphs and an O(k²) vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For EDP, we first prove that the problem is NP-complete on complete graphs. Then, we design an O(k^2.75) vertex kernel for [Figure presented] on split graphs, and improve it to a 7k+1 vertex kernel on threshold graphs. Lastly, we provide an O(k²) vertex kernel for [Figure presented] on block graphs and a 2k+1 vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al. (2015) [27].