论文标题
界定遗传图课程的中等宽度
Bounding the Mim-Width of Hereditary Graph Classes
论文作者
论文摘要
大量的NP-硬形图问题成为可在图形类别上溶解的多项式时间，其中MIM宽度是有界且可以快速计算的。因此，在解决特殊图类类别上的此类问题时，知道所考虑的图形类是否有限制MIM宽度是有帮助的。我们首先扩展了用于证明图形类中MIM宽度的（UN）界限的工具包。这使我们能够从遗传图类别的角度开始进行系统研究，以实现界限。对于给定的图形$ h $，当$ h $ free Graphs的类具有MIM宽度时，并且仅当它具有限制的集团宽度时。我们表明，对于$（H_1，H_2）$ - 免费图形而不是相同的。我们发现几个通用类别的$（H_1，H_2）$ - 免费的图形宽度，但MIM宽度是有限的，可以快速计算。我们还证明了许多新的结果，表明，对于某些$ H_1 $和$ H_2 $，$（H_1，H_2）$的类 - 免费图形的含量为MIM宽度。将这些结合与已知结果相结合，我们提出了当前最新状态的摘要定理，以$（H_1，H_2）$ - 免费图形的MIM宽度界限。
A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems on special graph classes, it is helpful to know whether the graph class under consideration has bounded mim-width. We first extend the toolkit for proving (un)boundedness of mim-width of graph classes. This enables us to initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes. For a given graph $H$, the class of $H$-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for $(H_1,H_2)$-free graphs. We find several general classes of $(H_1,H_2)$-free graphs having unbounded clique-width, but the mim-width is bounded and quickly computable. We also prove a number of new results showing that, for certain $H_1$ and $H_2$, the class of $(H_1,H_2)$-free graphs has unbounded mim-width. Combining these with known results, we present summary theorems of the current state of the art for the boundedness of mim-width for $(H_1,H_2)$-free graphs.
