论文标题
树木分解具有有限的独立数：超出独立集
Tree decompositions with bounded independence number: beyond independent sets
论文作者
论文摘要
我们继续研究图类类别，其中，由于存在一个具有有界树独立数量的图形类别，因此，由于存在一个大的集团，因此，由于存在大型集团，因此树宽只能很大。在[Dallard，Milanič和štorgel中，Treewidth与集团数字。 {II}。树独立的数字，2022]，结果表明，只要给出了输入图与具有有限的独立性的树木分解，可以在多项式时间内解决独立集和诱发匹配问题的常见概括和诱导的匹配问题的常见概括。我们提供了算法问题的进一步示例，这些算法问题可以在此假设下在多项式时间内解决。这包括，对于所有正整数$ d $，在距离上打包子图的问题至少至少$ d $（概括了最大重量独立包装问题）以及找到一个大型引起的稀疏子图的问题，该子图满足了在计算Monadic二阶逻辑中表达的任意但固定的属性。作为我们方法的一部分，我们将弦图的能力概括为一般图的上下文及其树独立数字的上下文。
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-independence number. In [Dallard, Milanič, and Štorgel, Treewidth versus clique number. {II}. Tree-independence number, 2022], it was shown that the Maximum Weight Independent Packing problem, which is a common generalization of the Independent Set and Induced Matching problems, can be solved in polynomial time provided that the input graph is given along with a tree decomposition with bounded independence number. We provide further examples of algorithmic problems that can be solved in polynomial time under this assumption. This includes, for all even positive integers $d$, the problem of packing subgraphs at distance at least $d$ (generalizing the Maximum Weight Independent Packing problem) and the problem of finding a large induced sparse subgraph satisfying an arbitrary but fixed property expressible in counting monadic second-order logic. As part of our approach, we generalize some classical results on powers of chordal graphs to the context of general graphs and their tree-independence numbers.
