Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT

摘要

Assume that a group of n people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known graph coloring problem (with n being the number of vertices) and it can be solved in O*(2(n)) time by the inclusion-exclusion principle as shown by Bjorklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in O*(2(n)) time is to use the Fast Fourier Transform (FFT). For this, given a graph G one constructs a polynomial PG(x) of degree O*(2(n)) with the following property: G is k-colorable if and only if the coefficient of x(m) (for some particular value of m) in the k-th power of P(x) is nonzero. Then, it remains to compute this coefficient using FFT.