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.ESA.2023.23
URN: urn:nbn:de:0030-drops-186769
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18676/
Bonnet, Édouard ;
Duron, Julien ;
Geniet, Colin ;
Thomassé, Stéphan ;
Wesolek, Alexandra
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄
Abstract
Dallard, Milanič, and Štorgel [arXiv '22] ask if, for every class excluding a fixed planar graph H as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when H is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when H is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the t-vertex cycle, C_t [Gartland et al., STOC '21], and the disjoint union of t triangles, tC₃ [Bonamy et al., SODA '23].
We give, for every integer t, a polynomial-time algorithm running in n^O(t⁵) when H is the friendship graph K₁ + tK₂ (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in n^{O(t² log n) + f(t)}, with f a single-exponential function, when H is tC₃ ⊎ C₄ (the disjoint union of t triangles and a 4-vertex cycle). The former generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding tK₂ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.’s result.
BibTeX - Entry
@InProceedings{bonnet_et_al:LIPIcs.ESA.2023.23,
author = {Bonnet, \'{E}douard and Duron, Julien and Geniet, Colin and Thomass\'{e}, St\'{e}phan and Wesolek, Alexandra},
title = {{Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18676},
URN = {urn:nbn:de:0030-drops-186769},
doi = {10.4230/LIPIcs.ESA.2023.23},
annote = {Keywords: Maximum Independent Set, forbidden induced minors, quasipolynomial-time algorithms}
}
|
Keywords: |
|
Maximum Independent Set, forbidden induced minors, quasipolynomial-time algorithms |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
