论文标题
主导的最小分离器是驯服的（几乎所有其他都是野性）
Dominated Minimal Separators are Tame (Nearly All Others are Feral)
论文作者
论文摘要
如果存在一个常数$ k $，则$ n $ vertices上的每个图中的每个图都包含一个常数$ k $，以使图形的$ {\ cal f} $称为{\ em tame}，以便在$ {\ cal f}中的每个图中包含$ o（n^k）$ minimal分离器的最小分隔符，{\ em quartly-quasi-quasi-quasi-quasi-quasi-quasi-quasi-quasi-quasi-quasi-quasi-quaSi-the $} $ O（n^{k \ log n}）$最小分隔符，并且{\ em feral}如果存在常数$ c> 1 $，以便$ {\ cal f} $包含$ n $ vertex图形，至少$ c^n $ c^n $ c^n $最小分离器，用于任意大型$ n $。将图类类别分为驯服或野性具有许多算法后果，并且最近受到了广泛的关注。 在寻求这种分类的过程中，关键的图理论对象是$ k $ - {\ em creature}的概念。在最近的手稿中[Abrishami等，Arxiv 2020]猜想，每个遗传级$ {\ cal f} $不包括$ k $ - 创建的某些固定常数$ k $的创建都是驯服的。我们对这个猜想进行了反例，并证明了较弱的结果：遗传级$ {\ cal f} $如果排除了某些固定常数$ k $的$ k $ - 创建$ k $ k $，并且每个最小分隔符都可以由另一个固定常数$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$ k'$。开发的工具还导致了独立兴趣的许多其他结果。 {\ bf（i）我们获得了由有限的禁止诱导的子图定义为强烈的准角色或野性的所有遗传图类别的完整分类。这概括了Milanič和Pivač[WG'19]。 {\ bf（ii）}我们表明，不包括$ k $创建的遗传级别，并将所有长度至少$ c $的周期排除在某些常数$ c $的情况下是驯服的。这概括了[Chudnovsky等，Arxiv 2019]的结果。 {\ bf（iii）}我们表明，每个不包括$ k $创建的遗传级别，并在某些固定常数$ c $的$ c $ Vertices上排除了完整的图形。
A class ${\cal F}$ of graphs is called {\em tame} if there exists a constant $k$ so that every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^k)$ minimal separators, {\em strongly-quasi-tame} if every graph in ${\cal F}$ on $n$ vertices contains at most $O(n^{k \log n})$ minimal separators, and {\em feral} if there exists a constant $c > 1$ so that ${\cal F}$ contains $n$-vertex graphs with at least $c^n$ minimal separators for arbitrarily large $n$. The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention. A key graph-theoretic object in the quest for such a classification is the notion of a $k$-{\em creature}. In a recent manuscript [Abrishami et al., Arxiv 2020] conjecture that every hereditary class ${\cal F}$ that excludes $k$-creatures for some fixed constant $k$ is tame. We give a counterexample to this conjecture and prove the weaker result that a hereditary class ${\cal F}$ is strongly quasi-tame if it excludes $k$-creatures for some fixed constant $k$ and additionally every minimal separator can be dominated by another fixed constant $k'$ number of vertices. The tools developed also lead to a number of additional results of independent interest. {\bf (i) We obtain a complete classification of all hereditary graph classes defined by a finite set of forbidden induced subgraphs into strongly quasi-tame or feral. This generalizes Milanič and Pivač [WG'19]. {\bf (ii)} We show that hereditary class that excludes $k$-creatures and additionally excludes all cycles of length at least $c$, for some constant $c$, are tame. This generalizes the result of [Chudnovsky et al., Arxiv 2019]. {\bf (iii)} We show that every hereditary class that excludes $k$-creatures and additionally excludes a complete graph on $c$ vertices for some fixed constant $c$ is tame.
