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. |

Published: 13th December 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.233.8 | bibtex | |

Comments and questions to: eptcs@eptcs.org |

For website issues: webmaster@eptcs.org |