Families with infants: speeding up algorithms for NP-hard problems using FFT

DOI10.1145/2847419MaRDI QIDQ4962612zbMATH OpenOpenAlexFDO

Authors Alexander Golovnev, Ivan Mihajlin, Alexander S. Kulikov

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.2209

zbMATH Keywords

algorithmschromatic numbercounting perfect matchingsfast Fourier transformNP-hard problemtraveling salesman

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Numerical methods for discrete and fast Fourier transforms (65T50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: Assume that a group of 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 coloring problem and it can be solved in $O^{\ast }(2^n)$ time by the inclusion-exclusion principle as shown by Bj"{o}rklund, Husfeldt, and Koivisto in 2009.Another approach to solve this problem in $O^{\ast }(2^n)$ time is to use the fast Fourier transform. A graph is $k$-colorable if and only if the $k$-th power of a polynomial containing a monomial $pro{d}_{i=1}^n{x}_i^{[iinI]}$ for each independent set $Isubseteq[n]$ of the graph, contains the monomial $x_1{x}_2\mathrm{...}{x}_n$. 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^{\ast }((2-varepsilon{)}^n)$ time. 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.

Recommendations

• Families with infants: a general approach to solve hard partition problems
• Faster exponential-time algorithms in graphs of bounded average degree
• Faster graph coloring in polynomial space
• Set partitioning via inclusion-exclusion
• Faster graph coloring in polynomial space

Cited in

(5)

• Families with infants: a general approach to solve hard partition problems
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• A space improved algorithm for chromatic number
• Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
• Faster edge coloring by partition sieving

This page was built for publication: Families with infants: speeding up algorithms for NP-hard problems using FFT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962612)