Header menu link for other important links
X
Parameterized Complexity of Set-Restricted Disjoint Paths on Chordal Graphs
P.A. Golovach, , A. Rai, S. Saurabh
Published in Springer Science and Business Media Deutschland GmbH
2022
Volume: 13296 LNCS
   
Pages: 152 - 169
Abstract
The Disjoint Paths problem takes as input a graph and pairs of terminals, and asks whether all the terminal pairs can be connected by paths that are vertex disjoint. It is known to be NP-complete even on interval graphs. On general graphs, the framework of Robertson and Seymour can be used to get an FPT result parameterized by the number of terminals, but the running time is very high. Considering this, there has been a lot of work on Disjoint Paths on restricted graph classes like planar graphs, chordal graphs, etc. In this work, we look at a generalization of the Disjoint Paths problem, namely Set-Restricted Disjoint Paths (SRDP), where in addition to terminal pairs, we are also given subsets of vertices as domains for each pair, and we want to connect the terminal pairs by vertex disjoint paths that use the vertices only from their respective domains. This problem is known to be in XP on chordal graphs. We show that the FPT result of Disjoint Paths on chordal graphs can be generalized to SRDP. In particular, we show that SRDP can be solved in time O∗(2 O(klogk)) on chordal graphs (here the O∗ notation hides the polynomial factors in the running time), where k is the number of terminal pairs. We complement this result by showing that SRDP does not have a polynomial kernel on interval graphs, a subclass of chordal graphs. © 2022, Springer Nature Switzerland AG.