Document Open Access Logo

Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

Author Tuukka Korhonen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2021.87.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Maximum weight independent set
  • Treewidth
  • Tropical circuits
  • Dynamic programming
  • Treedepth
  • Monotone circuit complexity

Metrics

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

Abstract

We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute with max and + operations. For a graph G, an MWIS-circuit of G is a tropical circuit whose inputs correspond to vertices of G and which computes the weight of a maximum weight independent set of G for any assignment of weights to the inputs. We show that if G has treewidth w and maximum degree d, then any MWIS-circuit of G has 2^{Ω(w/d)} gates and that if G is planar, or more generally H-minor-free for any fixed graph H, then any MWIS-circuit of G has 2^{Ω(w)} gates. An MWIS-formula is an MWIS-circuit where each gate has fan-out at most one. We show that if G has treedepth t and maximum degree d, then any MWIS-formula of G has 2^{Ω(t/d)} gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and H-minor-free graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.

Cite As Get BibTex

Tuukka Korhonen. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.87

Author Details

Tuukka Korhonen
  • Department of Computer Science, University of Helsinki, Finland

Funding

This work has been financially supported by Academy of Finland (grant 322869).

Acknowledgements

I wish to thank Prafullkumar Tale for suggesting to generalize the result from planar graphs to H-minor-free graphs. I also thank Matti Järvisalo, Andreas Niskanen, and anonymous reviewers for helpful comments.

References

  1. Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2008. Google Scholar
  2. Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory of Computing Systems, 64(5):861-914, 2020. URL: https://doi.org/10.1007/s00224-019-09930-2.
  3. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23(1):11-24, 1989. URL: https://doi.org/10.1016/0166-218X(89)90031-0.
  4. Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor network complexity of multilinear maps. In Avrim Blum, editor, Proceedings of the 10th Innovations in Theoretical Computer Science Conference, volume 124 of LIPIcs, pages 7:1-7:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.7.
  5. Markus Bläser and Christian Hoffmann. On the complexity of the interlace polynomial. In Susanne Albers and Pascal Weil, editors, Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, volume 1 of LIPIcs, pages 97-108. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2008. URL: https://doi.org/10.4230/LIPIcs.STACS.2008.1337.
  6. Maria Luisa Bonet, Toniann Pitassi, and Ran Raz. On interpolation and automatization for Frege systems. SIAM Journal on Computing, 29(6):1939-1967, 2000. URL: https://doi.org/10.1137/S0097539798353230.
  7. Irénée Briquel and Pascal Koiran. A dichotomy theorem for polynomial evaluation. In Rastislav Královic and Damian Niwinski, editors, Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, volume 5734 of Lecture Notes in Computer Science, pages 187-198. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03816-7_17.
  8. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Boolean-width of graphs. Theoretical Computer Science, 412(39):5187-5204, 2011. URL: https://doi.org/10.1016/j.tcs.2011.05.022.
  9. Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, and Fernando Sánchez Villaamil. Width, depth, and space: Tradeoffs between branching and dynamic programming. Algorithms, 11(7):98, 2018. URL: https://doi.org/10.3390/a11070098.
  10. Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. On the maximum weight independent set problem in graphs without induced cycles of length at least five. SIAM Journal on Discrete Mathematics, 34(2):1472-1483, 2020. URL: https://doi.org/10.1137/19M1249473.
  11. V. Chvátal. Determining the stability number of a graph. SIAM Journal on Computing, 6(4):643-662, 1977. URL: https://doi.org/10.1137/0206046.
  12. Wojciech Czerwinski, Wojciech Nadara, and Marcin Pilipczuk. Improved bounds for the excluded-minor approximation of treedepth. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, Proceedings of the 27th Annual European Symposium on Algorithms, volume 144 of LIPIcs, pages 34:1-34:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.34.
  13. Erik D. Demaine and MohammadTaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. URL: https://doi.org/10.1007/s00493-008-2140-4.
  14. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math., 20(2):357-371, 2006. URL: https://doi.org/10.1137/040616929.
  15. Paul Erdős and Joel Spencer. Lopsided Lovász local lemma and latin transversals. Discrete Applied Mathematics, 30(2-3):151-154, 1991. URL: https://doi.org/10.1016/0166-218X(91)90040-4.
  16. Fedor V. Fomin and Petr A. Golovach. Subexponential parameterized algorithms and kernelization on almost chordal graphs. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, Proceedings of the 28th Annual European Symposium on Algorithms, volume 173 of LIPIcs, pages 49:1-49:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.49.
  17. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
  18. Eugene C. Freuder and Michael J. Quinn. Taking advantage of stable sets of variables in constraint satisfaction problems. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 1076-1078. Morgan Kaufmann, 1985. URL: http://ijcai.org/Proceedings/85-2/Papers/082.pdf.
  19. Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407-420, 1981. URL: https://doi.org/10.1016/0022-0000(81)90040-4.
  20. Peter Gartland and Daniel Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 613-624. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00063.
  21. Christian Hoffmann. Exponential time complexity of weighted counting of independent sets. In Venkatesh Raman and Saket Saurabh, editors, Proceedings of the 5th International Symposium on Parameterized and Exact Computation, volume 6478 of Lecture Notes in Computer Science, pages 180-191. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17493-3_18.
  22. Laurent Hyafil. On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2):120-123, 1979. URL: https://doi.org/10.1137/0208010.
  23. Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings. Journal of the ACM, 29(3):874-897, 1982. URL: https://doi.org/10.1145/322326.322341.
  24. Stasys Jukna. Lower bounds for tropical circuits and dynamic programs. Theory of Computing Systems, 57(1):160-194, 2015. URL: https://doi.org/10.1007/s00224-014-9574-4.
  25. Stasys Jukna. Tropical complexity, sidon sets, and dynamic programming. SIAM Journal on Discrete Mathematics, 30(4):2064-2085, 2016. URL: https://doi.org/10.1137/16M1064738.
  26. Balagopal Komarath, Anurag Pandey, and C. S. Rahul. Graph homomorphism polynomials: Algorithms and complexity. CoRR, abs/2011.04778, 2020. URL: http://arxiv.org/abs/2011.04778.
  27. Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271-283, 1930. Google Scholar
  28. Yuan Li, Alexander A. Razborov, and Benjamin Rossman. On the AC⁰ complexity of subgraph isomorphism. SIAM Journal on Computing, 46(3):936-971, 2017. URL: https://doi.org/10.1137/14099721X.
  29. Daniel Lokshantov, Martin Vatshelle, and Yngve Villanger. Independent set in P₅-free graphs in polynomial time. In Chandra Chekuri, editor, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 570-581. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.43.
  30. Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari. Computing the maximum using (min, +) formulas. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, volume 83 of LIPIcs, pages 74:1-74:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.74.
  31. Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari. Shortest path length with bounded-alternation (min, +) formulas. International Journal of Advances in Engineering Sciences and Applied Mathematics, 11(1):68-74, 2019. URL: https://doi.org/10.1007/s12572-018-0229-6.
  32. J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3(1):23-28, 1965. Google Scholar
  33. Jaroslav Nesetril and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. URL: https://doi.org/10.1016/j.ejc.2011.01.006.
  34. Patric R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1-3):197-207, 2002. URL: https://doi.org/10.1016/S0166-218X(01)00290-6.
  35. Michał Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Transactions on Computation Theory, 9(4):18:1-18:36, 2018. URL: https://doi.org/10.1145/3154856.
  36. Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  37. L. G. Valiant. Negation can be exponentially powerful. Theoretical Computer Science, 12:303-314, 1980. URL: https://doi.org/10.1016/0304-3975(80)90060-2.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact