Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Families with infants : Speeding up algorithms for NP-hard problems using FFT. / Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan.
в: ACM Transactions on Algorithms, Том 12, № 3, 35, 04.2016.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Families with infants
T2 - Speeding up algorithms for NP-hard problems using FFT
AU - Golovnev, Alexander
AU - Kulikov, Alexander S.
AU - Mihajlin, Ivan
PY - 2016/4
Y1 - 2016/4
N2 - 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∗(2n) time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in O∗ (2n) time is to use the Fast Fourier Transform (FFT). For this, given a graph G one constructs a polynomial PG(x) of degree O∗ (2n) with the following property: G is k-colorable if and only if the coefficient of xm (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. Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear, then the problem can be solved in O∗ ((2 - ϵ)n) time, where ϵ is a positive constant independent of n. We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.
AB - 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∗(2n) time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in O∗ (2n) time is to use the Fast Fourier Transform (FFT). For this, given a graph G one constructs a polynomial PG(x) of degree O∗ (2n) with the following property: G is k-colorable if and only if the coefficient of xm (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. Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear, then the problem can be solved in O∗ ((2 - ϵ)n) time, where ϵ is a positive constant independent of n. We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.
KW - Algorithms
KW - Chromatic number
KW - Counting perfect matchings
KW - Fast Fourier transform
KW - NP-hard problem
KW - Traveling salesman
UR - http://www.scopus.com/inward/record.url?scp=84968782878&partnerID=8YFLogxK
U2 - 10.1145/2847419
DO - 10.1145/2847419
M3 - Article
AN - SCOPUS:84968782878
VL - 12
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 3
M1 - 35
ER -
ID: 49823827