2023/02/16 by Bonnet, Édouard, Duron, Julien, Geniet, Colin +2
#05C85 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2302.08182
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, Ct [Gartland et al., STOC '21] and the disjoint union of t triangles, tC3 [Bonamy et al., SODA '23]. We give, for every integer t, a polynomial-time algorithm running in nO(t5) when H is the friendship graph K1 + tK2 (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in n^O(t2 log n)+tO(1) when H is tC3 \uplus C4 (the disjoint union of t triangles and a 4-vertex cycle). The former extends a classical result on graphs excluding tK2 as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.'s result.