research-article

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

Authors:

Alexander Golovnev,

Alexander S. Kulikov,

Ivan MihajlinAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 12, Issue 3

Article No.: 35, Pages 1 - 17

https://doi.org/10.1145/2847419

Published: 25 April 2016 Publication History

Abstract

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ⁿ) time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in O*(2ⁿ) time is to use the Fast Fourier Transform (FFT). For this, given a graph G one constructs a polynomial P_G(x) of degree O*(2ⁿ) 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.

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 − ε)ⁿ) 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.

References

[1]

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. 2004. PRIMES is in P. Annals of Mathematics (2004), 781--793.

[2]

Stefan Arnborg, Jens Lagergren, and Detlef Seese. 1991. Easy problems for tree-decomposable graphs. Journal of Algorithms 12, 2 (1991), 308--340.

Digital Library

[3]

Eric Bax and Joel Franklin. 2002. A permanent algorithm with exp {Ω(n^1/3/2ln n)} expected speedup for 0-1 matrices. Algorithmica 32, 1 (2002), 157--162.

Digital Library

[4]

Richard Bellman. 1962. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM 9, 1 (January 1962), 61--63.

Digital Library

[5]

Andreas Björklund. 2010. Determinant sums for undirected Hamiltonicity. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS’10). 173--182.

Digital Library

[6]

Andreas Björklund. 2012. Counting perfect matchings as fast as Ryser. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 914--921.

Digital Library

[7]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010a. Narrow sieves for parameterized paths and packings. arXiv:1007.1161 (2010).

[8]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010b. Trimmed Moebius inversion and graphs of bounded degree. Theory of Computing Systems 47, 3 (2010), 637--654.

Digital Library

[9]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2012. The traveling salesman problem in bounded degree graphs. ACM Transactions on Algorithms 8, 2 (2012), 18.

Digital Library

[10]

Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. 2009. Set partitioning via inclusion-exclusion. SIAM Journal on Computing 39, 2 (2009), 546--563.

Digital Library

[11]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, (3rd. ed.). MIT Press.

Digital Library

[12]

Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2013. Fast Hamiltonicity checking via bases of perfect matchings. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC’13). 301--310.

Digital Library

[13]

Marek Cygan and Marcin Pilipczuk. 2010. Exact and approximate bandwidth. Theoretical Computer Science 411, 40--42 (2010), 3701--3713.

Digital Library

[14]

Marek Cygan and Marcin Pilipczuk. 2013. Faster exponential-time algorithms in graphs of bounded average degree. In Automata, Languages, and Programming. Lecture Notes in Computer Science, Vol. 7965. Springer, Berlin, 364--375.

Digital Library

[15]

Gabriel A. Dirac. 1952. Some theorems on abstract graphs. Proceedings of the London Mathematical Society 3, 1 (1952), 69--81.

[16]

Alexander Golovnev, Aleaxnder S. Kulikov, and Ivan Mihajlin. 2014. Families with infants: A general approach to solve hard partition problems. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), Lecture Notes in Computer Science, Vol. 8572. Springer, Berlin, 551--562.

[17]

Michael Held and Richard M. Karp. 1962. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics 10, 1 (1962), 196--210.

[18]

Taisuke Izumi and Tadashi Wadayama. 2012. A new direction for counting perfect matchings. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 591--598.

Digital Library

[19]

Ioannis Koutis and Ryan Williams. 2009. Limits and applications of group algebras for parameterized problems. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, (ICALP 2009), Lecture Notes in Computer Science, Vol. 5555, Part I. Springer, Berlin, 653--664.

Digital Library

[20]

Leopold Kronecker. 1882. Grundzüge einer arithmetischen theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik 92 (1882), 1--122.

[21]

Daniel Lokshtanov and Jesper Nederlof. 2010. Saving space by algebraization. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). ACM, 321--330.

Digital Library

[22]

Johan M. M. Rooij, Hans L. Bodlaender, and Peter Rossmanith. 2009. Dynamic programming on tree decompositions using generalised fast subset convolution. In Algorithms—ESA 2009, Amos Fiat and Peter Sanders (Eds.). Lecture Notes in Computer Science, Vol. 5757. Springer, Berlin, 566--577.

[23]

Herbert John Ryser. 1963. Combinatorial Mathematics. Mathematical Association of America, Washington, DC.

[24]

Rocco A. Servedio and Andrew Wan. 2005. Computing sparse permanents faster. Information Processing Letters 96, 3 (2005), 89--92.

Digital Library

[25]

Victor Shoup. 2009. A Computational Introduction to Number Theory and Algebra (2nd. ed.). Cambridge University Press.

Digital Library

Cited By

Björklund AKaski PMohar BShinkar IO'Donnell R(2024)The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both TrueProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649656(859-870)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649656
Nederlof JPawlewicz JSwennenhuis CWęgrzycki K(2023)A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive CombinatoricsSIAM Journal on Computing10.1137/22M147811252:6(1369-1412)Online publication date: 29-Nov-2023
https://doi.org/10.1137/22M1478112
Nederlof JPawlewicz JSwennenhuis CWęgrzycki KMarx D(2021)A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatoricsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458166(1682-1701)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458166

Index Terms

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Infinite families of 4-chromatic Grötzsch-Sachs graphs

Let G be a 4-regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such graphs, called ...
Intractability of Clique-Width Parameterizations

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are $W[1]$-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when ...
Bounds for the b-chromatic number of some families of graphs

In this paper we obtain some upper bounds for the b-chromatic number of K"1","s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 12, Issue 3

June 2016

408 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2930058

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 April 2016

Accepted: 01 November 2015

Revised: 01 November 2015

Received: 01 October 2014

Published in TALG Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Simons Foundation, and NSF
Government of the Russian Federation
President of the Russian Federation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)2

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Björklund AKaski PMohar BShinkar IO'Donnell R(2024)The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both TrueProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649656(859-870)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649656
Nederlof JPawlewicz JSwennenhuis CWęgrzycki K(2023)A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive CombinatoricsSIAM Journal on Computing10.1137/22M147811252:6(1369-1412)Online publication date: 29-Nov-2023
https://doi.org/10.1137/22M1478112
Nederlof JPawlewicz JSwennenhuis CWęgrzycki KMarx D(2021)A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatoricsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458166(1682-1701)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458166

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents