Algorithmic Applications of Hypergraph and Partition Containers

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 [ST15], Balogh, Morris and Samotij [BMS15]). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston [KW82], Sapozhenko [Sap01]), 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.