2026-07-22T14:07:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18676 2024-03-06T11:02:26Z ddc:004 open_access

Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄ Bonnet, Édouard Duron, Julien Geniet, Colin Thomassé, Stéphan Wesolek, Alexandra Maximum Independent Set forbidden induced minors quasipolynomial-time algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Julien Duron and Colin Geniet and Stéphan Thomassé and Alexandra Wesolek 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.23 urn:nbn:de:0030-drops-186769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode