License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.57
URN: urn:nbn:de:0030-drops-185914
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18591/
Johnson, Matthew ;
Martin, Barnaby ;
Pandey, Sukanya ;
Paulusma, Daniël ;
Smith, Siani ;
van Leeuwen, Erik Jan
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs
Abstract
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1,…,H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems.
We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.
BibTeX - Entry
@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57,
author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
title = {{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {57:1--57:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18591},
URN = {urn:nbn:de:0030-drops-185914},
doi = {10.4230/LIPIcs.MFCS.2023.57},
annote = {Keywords: forbidden subgraphs, independent feedback vertex set, treewidth}
}
|
Keywords: |
|
forbidden subgraphs, independent feedback vertex set, treewidth |
|
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.08.2023 |
