Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth

Authors Dániel Marx, Govind S. Sankar , Philipp Schepper



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.95.pdf
  • Filesize: 1.14 MB
  • 20 pages

Document Identifiers

Author Details

Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarland Informatics Campus, Saarbrücken, Germany
Govind S. Sankar
  • Indian Institute of Technology Madras, Chennai, India
Philipp Schepper
  • CISPA Helmholtz Center for Information Security, Saarland Informatics Campus, Saarbrücken, Germany
  • Saarbrücken Graduate School of Computer Science, Saarland Informatics Campus, Germany

Cite AsGet BibTex

Dániel Marx, Govind S. Sankar, and Philipp Schepper. Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.95

Abstract

In the General Factor problem, we are given an undirected graph G and for each vertex v ∈ V(G) a finite set B_v of non-negative integers. The task is to decide if there is a subset S ⊆ E(G) such that deg_S(v) ∈ B_v for all vertices v of G. Define the max-gap of a finite integer set B to be the largest d ≥ 0 such that there is an a ≥ 0 with [a,a+d+1] ∩ B = {a,a+d+1}. Cornuéjols showed in 1988 that if the max-gap of all sets B_v is at most 1, then the decision version of General Factor is polynomial-time solvable. This result was extended 2018 by Dudycz and Paluch for the optimization (i.e. minimization and maximization) versions. We present a general algorithm counting the number of solutions of a certain size in time #2 (M+1)^{tw}^{𝒪(1)}, given a tree decomposition of width tw, where M is the maximum integer over all B_v. By using convolution techniques from van Rooij (2020), we improve upon the previous (M+1)^{3tw}^𝒪(1) time algorithm by Arulselvan et al. from 2018. We prove that this algorithm is essentially optimal for all cases that are not trivial or polynomial time solvable for the decision, minimization or maximization versions. Our lower bounds show that such an improvement is not even possible for B-Factor, which is General Factor on graphs where all sets B_v agree with the fixed set B. We show that for every fixed B where the problem is NP-hard, our (max B+1)^tw^𝒪(1) algorithm cannot be significantly improved: assuming the Strong Exponential Time Hypothesis (SETH), no algorithm can solve B-Factor in time (max B+1-ε)^tw^𝒪(1) for any ε > 0. We extend this bound to the counting version of B-Factor for arbitrary, non-trivial sets B, assuming #SETH. We also investigate the parameterization of the problem by cutwidth. Unlike for treewidth, having a larger set B does not appear to make the problem harder: we give a 2^cutw^𝒪(1) algorithm for any B and provide a matching lower bound that this is optimal for the NP-hard cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • General Factor
  • General Matching
  • Treewidth
  • Cutwidth

Metrics

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

References

  1. Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, and Jannik Matuschke. Matchings with lower quotas: Algorithms and complexity. Algorithmica, 80(1):185-208, 2018. URL: https://doi.org/10.1007/s00453-016-0252-6.
  2. Claude Berge. Graphs and Hypergraphs. North-Holland mathematical library, Amsterdam, 1973. Google Scholar
  3. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 196-207. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_17.
  4. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. URL: https://doi.org/10.1093/comjnl/bxm037.
  5. Liming Cai and David W. Juedes. On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci., 67(4):789-807, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00074-6.
  6. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. 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 75-85. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_6.
  7. Gérard Cornuéjols. General factors of graphs. J. Comb. Theory, Ser. B, 45(2):185-198, 1988. URL: https://doi.org/10.1016/0095-8956(88)90068-8.
  8. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  9. Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. RAIRO Theor. Informatics Appl., 26:257-286, 1992. URL: https://doi.org/10.1051/ita/1992260302571.
  10. Radu Curticapean. Parity separation: A scientifically proven method for permanent weight loss. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 47:1-47:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.47.
  11. Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. 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 1650-1669. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch113.
  12. 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. ACM Trans. Algorithms, 12(3):41:1-41:24, 2016. URL: https://doi.org/10.1145/2925416.
  13. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  14. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3):12:1-12:46, 2018. URL: https://doi.org/10.1145/3148227.
  15. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.23.
  16. Xavier Dahan. Regular graphs of large girth and arbitrary degree. Comb., 34(4):407-426, 2014. URL: https://doi.org/10.1007/s00493-014-2897-6.
  17. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms, 10(4):21:1-21:32, 2014. URL: https://doi.org/10.1145/2635812.
  18. Szymon Dudycz and Katarzyna Paluch. Optimal general matchings. In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159 of Lecture Notes in Computer Science, pages 176-189. Springer, 2018. Full version: http://arxiv.org/abs/1706.07418. URL: https://doi.org/10.1007/978-3-030-00256-5_15.
  19. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  20. Paul Erdős and Horst Sachs. Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12(251-257):22, 1963. Google Scholar
  21. Geoffrey Exoo and Robert Jajcay. Recursive constructions of small regular graphs of given degree and girth. Discret. Math., 312(17):2612-2619, 2012. URL: https://doi.org/10.1016/j.disc.2011.10.021.
  22. Tomás Feder. Fanout limitations on constraint systems. Theor. Comput. Sci., 255(1-2):281-293, 2001. URL: https://doi.org/10.1016/S0304-3975(99)00288-1.
  23. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 142-151. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.10.
  24. Arne Hoffmann and Lutz Volkmann. On unique k-factors and unique [1, k]-factors in graphs. Discret. Math., 278(1-3):127-138, 2004. URL: https://doi.org/10.1016/S0012-365X(03)00248-6.
  25. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  26. Wilfried Imrich. Explicit construction of regular graphs without small cycles. Comb., 4(1):53-59, 1984. URL: https://doi.org/10.1007/BF02579157.
  27. Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The complexity of finding S-factors in regular graphs. Electron. Colloquium Comput. Complex., 26:40, 2019. URL: https://eccc.weizmann.ac.il/report/2019/040.
  28. Felix Lazebnik, Vasiliy A Ustimenko, and Andrew J Woldar. A new series of dense graphs of high girth. Bulletin of the American mathematical society, 32(1):73-79, 1995. Google Scholar
  29. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bull. EATCS, 105:41-72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.
  30. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  31. László Lovász. The factorization of graphs. II. Acta Mathematica Hungarica, 23(1-2):223-246, 1972. Google Scholar
  32. Silvio Micali and Vijay V. Vazirani. An O(sqrt(|v|) |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17-27. IEEE Computer Society, 1980. URL: https://doi.org/10.1109/SFCS.1980.12.
  33. Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520-531. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22993-0_47.
  34. Yossi Shiloach. Another look at the degree constrained subgraph problem. Inf. Process. Lett., 12(2):89-92, 1981. URL: https://doi.org/10.1016/0020-0190(81)90009-0.
  35. Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. URL: https://doi.org/10.1016/0304-3975(79)90044-6.
  36. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. URL: https://doi.org/10.1137/0208032.
  37. Johan M. M. van Rooij. Fast algorithms for join operations on tree decompositions. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 262-297. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-42071-0_18.
  38. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
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