### 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 language | English |
---|---|

Title of host publication | 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 |

Editors | Viliam Geffert, Bart Preneel, Branislav Rovan, Julius Stuller, A Min Tjoa |

Publisher | Springer Singapore |

Pages | 315-326 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-319-04298-5 |

ISBN (Print) | 978-3-319-04297-8 |

DOIs | |

Publication status | Published - 2014 |

Externally published | Yes |

Event | 40th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2014 - Nový Smokovec, Slovakia Duration: 25 Jan 2014 → 30 Jan 2014 Conference number: 40 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 8327 |

### Conference

Conference | 40th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2014 |
---|---|

Abbreviated title | SOFSEM 2014 |

Country | Slovakia |

City | Nový Smokovec |

Period | 25/01/14 → 30/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