Finding disjoint paths in split graphs

Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen, Reza Saei

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

The well-known DISJOINT PATHS problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to be NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP ⊆ coNP/poly. We prove that DISJOINT PATHS remains NP-complete on split graphs, and show that the problem admits a kernel with O(k 2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k 3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.
Original languageEnglish
Pages (from-to)140-159
JournalTheory of computing systems
Volume57
DOIs
Publication statusPublished - 2015
Externally publishedYes

Fingerprint Dive into the research topics of 'Finding disjoint paths in split graphs'. Together they form a unique fingerprint.

  • Cite this