Scholarlink

<p>Dallard, Milanič, and Štorgel [arXiv ’22] ask if, for every class excluding a fixed planar graph <i>H</i> as an induced minor, <span>Maximum Independent Set</span> can be solved in polynomial time, and show that this is indeed the case when <i>H</i> 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 <i>H</i> 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 <i>t</i>-vertex cycle, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(C_t\)</EquationSource> </InlineEquation> [Gartland et al., STOC ’21], and the disjoint union of <i>t</i> triangles, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(tC_3\)</EquationSource> </InlineEquation> [Bonamy et al., SODA ’23]. We give, for every integer <i>t</i>, a polynomial-time algorithm running in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(n^{O(t^5)}\)</EquationSource> </InlineEquation> when <i>H</i> is the friendship graph <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(K_1 + tK_2\)</EquationSource> </InlineEquation> (<i>t</i> disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(n^{O(t^2 \log n)+f(t)}\)</EquationSource> </InlineEquation>, with <i>f</i> a single-exponential function, when <i>H</i> is <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(tC_3 \uplus C_4\)</EquationSource> </InlineEquation> (the disjoint union of <i>t</i> triangles and a 4-vertex cycle). The former generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(tK_2\)</EquationSource> </InlineEquation> as an induced subgraph [Alekseev, DAM ’07], while the latter extends Bonamy et&#xa0;al.’s result.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maximum Independent Set when Excluding an Induced Minor: \(K_1 + tK_2\) and \(tC_3 \uplus C_4\)

  • 期刊论文

  • 发表日期：

    2025年12月23日

查看全文
  • Édouard Bonnet,
  • Julien Duron,
  • Colin Geniet,
  • Stéphan Thomassé,
  • Alexandra Wesolek

摘要

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 generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding \(tK_2\) as an induced subgraph [Alekseev, DAM ’07], while the latter extends Bonamy et al.’s result.