Faster Graph Coloring in Polynomial Space
Faster Graph Coloring in Polynomial Space
复制标题
多项式空间中更快的图形着色
作者：
Serge Gaspers;Edward J. Lee
我们给出了一个多项式空间算法，它在时间$$O(1.1389^n)$$O(1.1389n)，对于最大度为3且时间为$$O(1.2356^n)$$O(1.2356n)，其中n是输入图中的顶点数。以及比约克伦德、胡斯费尔特和柯伊维斯托的包含-排除方法[SIAM J.Comput]。，这为运行时间为$$O(2.2356^n)$$O(2.2356n)和指数空间$$O(1.2330^n)$$O(1.2330n)用于计算独立集的时间算法。我们的主要算法计算最大度不超过3的图中的独立集，并且没有三个度为3的邻居的顶点。这个多项式空间算法是使用最近引入的分离、测量和征服方法[Gaspers&Sorkin，ICALP 2015]设计和分析的。使用Wahlström的复合测度法，这种小度图运行时间的改进被引导到更大的度，从而给出了对一般图的改进。将这两种方法结合在一起会导致在选择小度情况下的分支顶点时存在一定的灵活性，我们通过结构图的属性来应对这一点。
We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time $$O(1.1389^n)$$ O ( 1 . 1389 n ) for graphs with maximum degree 3 and in time $$O(1.2356^n)$$ O ( 1 . 2356 n ) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Björklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time $$O(2.2356^n)$$ O ( 2 . 2356 n ) as well as an exponential-space $$O(1.2330^n)$$ O ( 1 . 2330 n ) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlström’s compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.