Parameterized Complexity of Set-Restricted Disjoint Paths on Chordal Graphs

Golovach, Petr A. and Panolan, Fahad and Rai, Ashutosh and et al, . (2022) Parameterized Complexity of Set-Restricted Disjoint Paths on Chordal Graphs. In: 17th International Computer Science Symposium in Russia, CSR 2022, 29 June 2022through 1 July 2022, Virtual, Online.

Full text not available from this repository. (Request a copy)

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.

[error in script]

IITH Creators: