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_3$ [Bonamy et al., SODA '23]. We give, for every integer $t$, a polynomial-time algorithm running in $n^{O(t^5)}$ when $H$ is the friendship graph $K_1 + tK_2$ ($t$ disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in $n^{O(t^2 \log n)+f(t)}$, with $f$ a single-exponential function, when $H$ is $tC_3 \uplus C_4$ (the disjoint union of $t$ triangles and a 4-vertex cycle). The former extends a classical result on graphs excluding $tK_2$ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.'s result.
翻译:Dallard、Milanič和Štorgel [arXiv '22] 提出疑问:对于每个排除固定平面图$H$作为诱导子式的图类,最大独立集问题是否都能在多项式时间内求解;他们证明了当$H$是任何平面完全二分图、5顶点团减去一条边、或减去两条不相交边时,情况确实如此。若该问题得到肯定回答,将构成对现有技术的深远推广,因为目前我们尚不知道当$H$是7顶点路径时是否存在多项式时间算法。若将可处理性放宽至拟多项式时间算法的存在性,我们的认知则更为深入。事实上,针对$t$顶点环$C_t$ [Gartland等,STOC '21] 以及$t$个不相交三角形$tC_3$的并集 [Bonamy等,SODA '23],近期已获得拟多项式时间算法。对于任意整数$t$,我们给出:当$H$为友谊图$K_1 + tK_2$($t$条不相交边加上一个与它们全相邻的顶点)时,存在$n^{O(t^5)}$时间复杂度的多项式时间算法;当$H$为$tC_3 \uplus C_4$($t$个三角形与一个4顶点环的不相交并集)时,存在$n^{O(t^2 \log n)+f(t)}$时间复杂度的拟多项式时间算法,其中$f$为单指数函数。前者扩展了关于排除$tK_2$作为诱导子图的经典结果 [Alekseev, DAM '07],而后者扩展了Bonamy等人的结果。