Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Johnson, Matthew; Martin, Barnaby; Pandey, Sukanya; Paulusma, Daniël; Smith, Siani; Van Leeuwen, Erik Jan
Authors
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Sukanya Pandey
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy
Erik Jan Van Leeuwen
Abstract
For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp 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 H-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.
Citation
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
Conference Name | 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
---|---|
Conference Location | Bordeaux, France |
Start Date | Aug 28, 2023 |
End Date | Sep 1, 2023 |
Acceptance Date | Jul 18, 2023 |
Online Publication Date | Aug 21, 2023 |
Publication Date | Aug 21, 2023 |
Deposit Date | Dec 29, 2023 |
Publicly Available Date | Jan 2, 2024 |
Volume | 272 |
Pages | 57:1-57:15 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Book Title | 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
ISBN | 9783959772921 |
DOI | https://doi.org/10.4230/LIPIcs.MFCS.2023.57 |
Keywords | 2012 ACM Subject Classification Mathematics of computing → Graph theory; Theory of computa- tion → Graph algorithms analysis; Theory of computation → Problems, reductions and completeness Keywords and phrases forbidden subgraphh; independent feedbac |
Public URL | https://durham-repository.worktribe.com/output/2063724 |
Related Public URLs | https://research-information.bris.ac.uk/en/publications/complexity-framework-for-forbidden-subgraphs-iii-when-problems-ar |
Files
Published Conference Paper
(816 Kb)
PDF
Licence
http://creativecommons.org/licenses/by/4.0/
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search