Anti-Path Cover on Sparse Graph Classes

Pavel Dvořák
(Computer Science Institute of Charles University Charles University Prague, Czech Republic)
Dušan Knop
(Department of Applied Mathematics Charles University Prague, Czech Republic)
Tomáš Masařík
(Department of Applied Mathematics Charles University Prague, Czech Republic)

We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vertex disjoint paths in the complement of the input graph. More precisely, we show that if a graph has tree-width at most w and its complement is closed under Bondy-Chvatal closure, then it is possible to bound neighborhood diversity of the complement by a function of w only. A simpler proof where tree-depth is used instead of tree-width is also presented.

In Jan Bouda, Lukáš Holík, Jan Kofroň, Jan Strejček and Adam Rambousek: Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2016), Telč, Czech Republic, 21st-23rd October 2016, Electronic Proceedings in Theoretical Computer Science 233, pp. 82–86.
Published: 13th December 2016.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: