Finding disjoint paths in split graphs
Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen and Reza Saei
Theory of Computing Systems, Theory of Computing Systems, vol. 57, no. 1, pp. 140-159, 2015.
[DOI][Preprint]
This paper appeared in the proceedings of SOFSEM 2014, the 40th International Conference on Current Trends in Theory and Practice of Computer Science (held on January 25-30, 2014 in Nový Smokovec, Slovakia), Lecture Notes in Computer Science, vol. 8327, pp. 315-326, 2014.
[DOI]
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(k2) 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(k3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.