Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Matthew Johnson; Barnaby Martin; Sukanya Pandey; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen

doi:10.4230/LIPIcs.MFCS.2023.57

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Matthew Johnson^*, Barnaby Martin^*, Sukanya Pandey^*, Daniël Paulusma^*, Siani Smith^*, Erik Jan van Leeuwen^*

^*Corresponding author for this work

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

3 Citations (Scopus)

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.

Original language	English
Title of host publication	48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
Editors	Jerome Leroux, Sylvain Lombardy, David Peleg
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772921
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2023.57
Publication status	Published - Aug 2023
Event	48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 - Bordeaux, France Duration: 28 Aug 2023 → 1 Sept 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	272
ISSN (Print)	1868-8969

Conference

Conference	48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
Country/Territory	France
City	Bordeaux
Period	28/08/23 → 1/09/23

Bibliographical note

Funding Information:
We are grateful to Jelle Oostveen and Hans Bodlaender for useful discussions.

Publisher Copyright:
© Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen;

Keywords

forbidden subgraphs
independent feedback vertex set
treewidth

Access to Document

10.4230/LIPIcs.MFCS.2023.57

Handle.net

Persistent link

Cite this

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 J. Leroux, S. Lombardy, & D. Peleg (Eds.), 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 Article 57 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2023.57

Johnson, Matthew ; Martin, Barnaby ; Pandey, Sukanya et al. / Complexity Framework for Forbidden Subgraphs III : When Problems Are Tractable on Subcubic Graphs. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. editor / Jerome Leroux ; Sylvain Lombardy ; David Peleg. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{8722811b74704d9da9e847d7ce5993b5,

title = "Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs",

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

keywords = "forbidden subgraphs, independent feedback vertex set, treewidth",

author = "Matthew Johnson and Barnaby Martin and Sukanya Pandey and Dani{\"e}l Paulusma and Siani Smith and {van Leeuwen}, {Erik Jan}",

note = "Funding Information: We are grateful to Jelle Oostveen and Hans Bodlaender for useful discussions. Publisher Copyright: {\textcopyright} Matthew Johnson, Barnaby Martin, Sukanya Pandey, Dani{\"e}l Paulusma, Siani Smith, and Erik Jan van Leeuwen;; 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 ; Conference date: 28-08-2023 Through 01-09-2023",

year = "2023",

month = aug,

doi = "10.4230/LIPIcs.MFCS.2023.57",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",

booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023",

}

Johnson, M, Martin, B, Pandey, S, Paulusma, D, Smith, S & van Leeuwen, EJ 2023, Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. in J Leroux, S Lombardy & D Peleg (eds), 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023., 57, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, France, 28/08/23. https://doi.org/10.4230/LIPIcs.MFCS.2023.57

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. / Johnson, Matthew; Martin, Barnaby; Pandey, Sukanya et al.
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. ed. / Jerome Leroux; Sylvain Lombardy; David Peleg. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 57 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Complexity Framework for Forbidden Subgraphs III

T2 - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

AU - Johnson, Matthew

AU - Martin, Barnaby

AU - Pandey, Sukanya

AU - Paulusma, Daniël

AU - Smith, Siani

AU - van Leeuwen, Erik Jan

N1 - Funding Information: We are grateful to Jelle Oostveen and Hans Bodlaender for useful discussions. Publisher Copyright: © Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen;

PY - 2023/8

Y1 - 2023/8

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

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

KW - forbidden subgraphs

KW - independent feedback vertex set

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=85171435954&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2023.57

DO - 10.4230/LIPIcs.MFCS.2023.57

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85171435954

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

A2 - Leroux, Jerome

A2 - Lombardy, Sylvain

A2 - Peleg, David

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 28 August 2023 through 1 September 2023

ER -

Johnson M, Martin B, Pandey S, Paulusma D, Smith S, van Leeuwen EJ. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In Leroux J, Lombardy S, Peleg D, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 57. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2023.57

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this