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:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: chordal graphs; disjoint paths; fpt; kernel; set restricted disjoint paths
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 15 Oct 2022 06:42
Last Modified: 15 Oct 2022 06:42
URI: http://raiith.iith.ac.in/id/eprint/10959
Publisher URL: http://doi.org/10.1007/978-3-031-09574-0_10
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10959 Statistics for this ePrint Item