Document Open Access Logo

Finding Large Set Covers Faster via the Representation Method

Author Jesper Nederlof

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.69.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Jesper Nederlof

Cite As Get BibTex

Jesper Nederlof. Finding Large Set Covers Faster via the Representation Method. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 69:1-69:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.69

Abstract

The worst-case fastest known algorithm for the Set Cover problem on universes with n elements still essentially is the simple O^*(2^n)-time dynamic programming algorithm, and no non-trivial consequences of an O^*(1.01^n)-time algorithm are known. Motivated by this chasm, we study the following natural question: Which instances of Set Cover can we solve faster than the simple dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm that determines the existence of a set cover of size sigma*n in O^*(2^{(1-Omega(sigma^4))n}) time. Our approach is also applicable to Set Cover instances with exponentially many sets: By reducing the task of finding the chromatic number chi(G) of a given n-vertex graph G to Set Cover in the natural way, we show there is an O^*(2^{(1-Omega(sigma^4))n})-time randomized algorithm that given integer s = sigma*n, outputs NO if chi(G) > s  and YES with constant probability if \chi(G) <= s - 1.

On a high level, our results are inspired by the "representation method" of Howgrave-Graham and Joux~[EUROCRYPT'10] and obtained by only evaluating a randomly sampled subset of the table entries of a dynamic programming algorithm.

Subject Classification

Keywords
  • Set Cover
  • Exact Exponential Algorithms
  • Fine-Grained Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset sum in the absence of concentration. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 48-61. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://www.dagstuhl.de/dagpub/978-3-939897-78-1, URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.48.
  2. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense subset sum may be the hardest. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.13.
  3. Anja Becker, Jean-Sébastien Coron, and Antoine Joux. Improved generic algorithms for hard knapsacks. In Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pages 364-385. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20465-4_21.
  4. Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in 2 n/20: How 1 + 1 = 0 improves information set decoding. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 520-536. Springer, 2012. Talk at http://www.iacr.org/cryptodb/data/paper.php?pubkey=24271. URL: http://dx.doi.org/10.1007/978-3-642-29011-4_31.
  5. Andreas Björklund. Uniquely coloring graphs over path decompositions. CoRR, abs/1504.03670, 2015. URL: http://arxiv.org/abs/1504.03670.
  6. Andreas Björklund, Holger Dell, and Thore Husfeldt. The parity of set systems under random restrictions with applications to exponential time problems. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 231-242. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_19.
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. CoRR, abs/1007.1161, 2010. URL: http://arxiv.org/abs/1007.1161.
  8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Trimmed moebius inversion and graphs of bounded degree. Theory Comput. Syst., 47(3):637-654, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9185-7.
  9. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. ACM Transactions on Algorithms, 8(2):18, 2012. URL: http://dx.doi.org/10.1145/2151171.2151181.
  10. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: http://dx.doi.org/10.1137/070683933.
  11. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 252-260. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/CCC.2006.6.
  12. Timothy M. Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch87.
  13. Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. Comput., 24(5):1036-1050, 1995. URL: http://dx.doi.org/10.1137/S0097539793250330.
  14. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. In Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012, pages 74-84. IEEE, 2012. URL: http://dx.doi.org/10.1109/CCC.2012.36.
  15. Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput., 243:75-85, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.007.
  16. Vilhelm Dahllöf. Exact Algorithms for Exact Satisfiability Problems. PhD thesis, Linköping University, TCSLAB, The Institute of Technology, 2006. Google Scholar
  17. Evgeny Dantsin, Andreas Goerdt, Edward A Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and Uwe Schöning. A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theoretical Computer Science, 289(1):69-83, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00174-8.
  18. Limor Drori and David Peleg. Faster exact solutions for some NP-hard problems. Theoretical Computer Science, 287(2):473-499, 2002. Algorithms. URL: http://dx.doi.org/10.1016/S0304-3975(01)00257-2.
  19. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5), 2009. URL: http://dx.doi.org/10.1145/1552285.1552286.
  20. Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. Families with infants: A general approach to solve hard partition problems. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 551-562. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_46.
  21. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. Google Scholar
  22. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. J. ACM, 21(2):277-292, 1974. URL: http://dx.doi.org/10.1145/321812.321823.
  23. Nick Howgrave-Graham and Antoine Joux. New generic algorithms for hard knapsacks. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 235-256. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13190-5_12.
  24. Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports, 3(8):40-72, 2013. URL: http://dx.doi.org/10.4230/DagRep.3.8.40.
  25. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider. 0-1 integer linear programming with a linear number of constraints. CoRR, abs/1401.5512, 2014. URL: http://arxiv.org/abs/1401.5512.
  26. Antoine Joux. Algorithmic Cryptanalysis. Chapman &Hall/CRC, 1st edition, 2009. Google Scholar
  27. Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Homomorphic hashing for sparse coefficient extraction. In Dimitrios M. Thilikos and Gerhard J. Woeginger, editors, Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings, volume 7535 of Lecture Notes in Computer Science, pages 147-158. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33293-7_15.
  28. Mikko Koivisto. Partitioning into sets of bounded cardinality. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 258-263. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-11269-0_21.
  29. Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider. Model counting for cnf formulas of bounded modular treewidth. Algorithmica, pages 1-27, 2015. URL: http://dx.doi.org/10.1007/s00453-015-0030-x.
  30. Sigve Hortemo Sæther, Jan Arne Telle, and Martin Vatshelle. Solving maxsat and #sat on structured CNF formulas. In Carsten Sinz and Uwe Egly, editors, Theory and Applications of Satisfiability Testing - SAT 2014, Vienna, Austria, July 14-17, 2014. Proceedings, volume 8561 of Lecture Notes in Computer Science, pages 16-31. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-09284-3_3.
  31. Uwe Schöning. A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica, 32(4):615-623, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0094-7.
  32. Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact