论文标题
树宽与集团数字。 iii。具有禁止结构的图形独立数量
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
论文作者
论文摘要
我们继续研究$（\ mathrm {tw}，ω）$有限的图形类别，即，由于存在一个大集团，该属性的目的是了解该属性对独立集和相关问题的有用算法含义的程度。在该系列的上一篇论文[Dallard，Milanič和štorgel，Treewidth与集团数字。 ii。树独立的数字]，我们引入了树独立数字，这是与树分解相关的最小最大图形。有界树独立数的数字意味着$（\ mathrm {tw}，ω）$ - 有限性和对于最大重量独立设置问题的多项式时间算法的存在，前提是输入图与有限的独立数字一起给出了树的分解图。 在本文中，我们考虑了六个图形遏制关系，并且每个图都表征了图形$ h $，任何图形不包括$ h $相对于关系，都可以允许具有有界独立数字的树分解。引起的次要关系特别令人感兴趣：我们表明，不包括$ k_5 $减去边缘或4美元的$ 4 $ - 旋转意味着存在一个树的存在，其中每个袋子每个袋子最多是一个集团加上$ 3 $的顶点，而不包括完整的bipartite图$ k_ {2，q} $ in Indeptions $ n nordecorse $ n nordections $ nordections $独立$ 2）我们的建设性证明是使用多种工具获得的，包括$ \ ell $缩放的树木分解，SPQR树和潜在的最大簇。它们暗示了独立集合的多项式时间算法以及无限的图形类别中的相关问题；特别是，结果适用于2019年$ 1 $ - 完美定向的图表，回答了Beisegel，Chudnovsky，Gurvich，Milanič和Servatius的问题。
We continue the study of $(\mathrm{tw},ω)$-bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number], we introduced the tree-independence number, a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both $(\mathrm{tw},ω)$-boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Set problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In this paper, we consider six graph containment relations and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a $K_5$ minus an edge or the $4$-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most $3$ vertices, while excluding a complete bipartite graph $K_{2,q}$ implies the existence of a tree decomposition with independence number at most $2(q-1)$. Our constructive proofs are obtained using a variety of tools, including $\ell$-refined tree decompositions, SPQR trees, and potential maximal cliques. They imply polynomial-time algorithms for the Independent Set and related problems in an infinite family of graph classes; in particular, the results apply to the class of $1$-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019.
