Finding disjoint paths in split graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 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
Title of host publicationSOFSEM 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings
EditorsViliam Geffert, Bart Preneel, Branislav Rovan, Julius Stuller, A Min Tjoa
PublisherSpringer Singapore
Pages315-326
Number of pages12
ISBN (Electronic)978-3-319-04298-5
ISBN (Print)978-3-319-04297-8
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event40th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2014 - Nový Smokovec, Slovakia
Duration: 25 Jan 201430 Jan 2014
Conference number: 40

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8327

Conference

Conference40th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2014
Abbreviated titleSOFSEM 2014
CountrySlovakia
CityNový Smokovec
Period25/01/1430/01/14

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

  • Cite this

    Heggernes, P., van 't Hof, P., Leeuwen, E. J. V., & Saei, R. (2014). Finding disjoint paths in split graphs. In V. Geffert, B. Preneel, B. Rovan, J. Stuller, & A. M. Tjoa (Eds.), SOFSEM 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings (pp. 315-326). (Lecture Notes in Computer Science; Vol. 8327). Springer Singapore. https://doi.org/10.1007/978-3-319-04298-5_28