论文标题
超图和分区容器的算法应用
Algorithmic Applications of Hypergraph and Partition Containers
论文作者
论文摘要
我们提出了一种通用方法，将算法转换为更快的算法，以进行几乎规范的输入实例。在非正式的情况下，几乎规范的输入是一个输入，其中最大程度大于平均程度的最多恒定因素。这个投入家族大大概括了几种投入族，我们通常会改善算法，包括有界度的输入和随机输入。它还概括了我们通常没有更快算法的投入家族，包括任意高度和非常密集的输入的常规输入。我们采用我们的方法来实现几个中央NP完整问题的精确算法中的突破，包括$ K $ -SAT，图形着色和最大独立集。 我们的主要工具是相对较新的HyperGraph容器方法的第一个算法应用（Saxton and Thomason 2015，Balogh，Morris和Samotij 2015）。这一最近的突破概括了图形的早期版本（Kleitman和Winston 1982，Sapozhenko 2001），近年来已广泛用于极端组合学。我们工作的一个重要组成部分是（超）图容器对隔板容器的概括。
We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This family of inputs vastly generalizes several families of inputs for which we commonly have improved algorithms, including bounded-degree inputs and random inputs. It also generalizes families of inputs for which we don't usually have faster algorithms, including regular-inputs of arbitrarily high degree and very dense inputs. We apply our method to achieve breakthroughs in exact algorithms for several central NP-Complete problems including $k$-SAT, Graph Coloring, and Maximum Independent Set. Our main tool is the first algorithmic application of the relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston 1982, Sapozhenko 2001), has been used extensively in recent years in extremal combinatorics. An important component of our work is the generalization of (hyper-)graph containers to Partition Containers.
