论文标题
覆盖最小的分离器和潜在的最大集团在$ p_t $ - 免费图形中
Covering minimal separators and potential maximal cliques in $P_t$-free graphs
论文作者
论文摘要
如果图形不包含$ t $ -vertex路径作为诱导子图，则将图称为$ p_t $ -free}。虽然$ p_4 $ - free图是cographs，但$ p_t $ for-free图的结构对$ t \ geq 5 $却几乎没有理解。一方面，众所周知，经典的计算问题，例如最大重量独立集（MWIS）和$ 3 $颜色的颜色，对于任何固定的$ t $而言，在$ p_t $ -free图上都不是NP-HARD。另一方面，尽管付出了巨大的努力，但MWIS的多项式时间算法在$ p_6 $ -free Graphs〜 [SODA 2019]和$ 3 $ - $ p_7 $ -free Graphs〜 [Combinatorica 2018]中才发现。在这两种情况下，算法都依赖于对所考虑的图类别的深层结构见解。 MWIS算法中的主要工具之一是$ p_5 $ -free Graphs〜 [SODA 2014]和$ P_6 $ -FREE GRAPHS〜[SODA 2019]是所谓的分离器，这些分隔符覆盖了Lemma，这些分隔符断言，该图中每个最小分离器都可以被一个恒定数量的恒定数字的邻里覆盖。在本说明中，我们表明，这样的语句概括为$ p_7 $ - free图，并且在$ p_8 $ free图中为false。我们还讨论了这种陈述的类似物，以涵盖与社区工会的潜在最大集团。
A graph is called $P_t$-free} if it does not contain a $t$-vertex path as an induced subgraph. While $P_4$-free graphs are exactly cographs, the structure of $P_t$-free graphs for $t \geq 5$ remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and $3$-Coloring are not known to be NP-hard on $P_t$-free graphs for any fixed $t$. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in $P_6$-free graphs~[SODA 2019] and $3$-Coloring in $P_7$-free graphs~[Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in $P_5$-free graphs~[SODA 2014] and in $P_6$-free graphs~[SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to $P_7$-free graphs and is false in $P_8$-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.
