2026-07-26T02:16:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19429 2024-03-06T11:04:02Z ddc:004 open_access

Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs Chaudhary, Juhi Gahlawat, Harmender Włodarczyk, Michal Zehavi, Meirav Kernelization Parameterized Complexity Vertex-Disjoint Paths Problem Edge-Disjoint Paths Problem Given an undirected graph G and a multiset of k terminal pairs 𝒳, the Vertex-Disjoint Paths (VDP) and Edge-Disjoint Paths (EDP) problems ask whether G has k pairwise internally vertex-disjoint paths and k pairwise edge-disjoint paths, respectively, connecting every terminal pair in 𝒳. In this paper, we study the kernelization complexity of VDP and EDP on subclasses of chordal graphs. For VDP, we design a 4k vertex kernel on split graphs and an 𝒪(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 𝒪(k^{2.75}) vertex kernel for EDP on split graphs, and improve it to a 7k+1 vertex kernel on threshold graphs. Lastly, we provide an 𝒪(k²) vertex kernel for EDP 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. [Theory Comput. Syst., 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juhi Chaudhary and Harmender Gahlawat and Michal Włodarczyk and Meirav Zehavi 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.10 urn:nbn:de:0030-drops-194296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.10 eng https://creativecommons.org/licenses/by/4.0/legalcode