Partitioning H-free graphs of bounded diameter

Brause, C.; Golovach, P. A.; Martin, B.; Paulusma, D.; Smith, S.

doi:10.4230/lipics.isaac.2021.21

Partitioning H-free graphs of bounded diameter

Brause, C.; Golovach, P. A.; Martin, B.; Paulusma, D.; Smith, S.

Authors

C. Brause

P. A. Golovach

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy

Contributors

Hee-Kap Ahn
Editor

Kunihiko Sadakane
Editor

Abstract

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph H contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study (MFCS 2019) on the k-Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the H-free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to H-free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3- Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.

Citation

Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn, & K. Sadakane (Eds.), . https://doi.org/10.4230/lipics.isaac.2021.21

Conference Name	32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Conference Location	Fukuoka, Japan
Start Date	Dec 6, 2021
End Date	Dec 8, 2021
Acceptance Date	Sep 6, 2021
Online Publication Date	Nov 30, 2021
Publication Date	2021
Deposit Date	Oct 23, 2021
Publicly Available Date	Jan 17, 2023
Pages	21:1-21:14
Series Title	Leibniz International Proceedings in Informatics
Series ISSN	1868-8969
DOI	https://doi.org/10.4230/lipics.isaac.2021.21
Public URL	https://durham-repository.worktribe.com/output/1138258

Files

Published Conference Proceeding (736 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© Christoph Brause, Petr Golovach, Barnaby Martin, Daniël Paulusma, and Siani Smith;
licensed under Creative Commons License CC-BY 4.0