Document Open Access Logo

Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard)

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.22.pdf
  • Filesize: 1.07 MB
  • 23 pages

Document Identifiers

Author Details

Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Govind S. Sankar
  • Duke University, Durham, NC, USA
Philipp Schepper
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Funding

Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.
  • Schepper, Philipp: Part of Saarbrücken Graduate School of Computer Science, Germany.

Cite As Get BibTex

Dániel Marx, Govind S. Sankar, and Philipp Schepper. Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard). In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.22

Abstract

In the general AntiFactor problem, a graph G and, for every vertex v of G, a set X_v ⊆ ℕ of forbidden degrees is given. The task is to find a set S of edges such that the degree of v in S is not in the set X_v. Standard techniques (dynamic programming plus fast convolution) can be used to show that if M is the largest forbidden degree, then the problem can be solved in time (M+2)^{tw}⋅n^{O(1)} if a tree decomposition of width tw is given. However, significantly faster algorithms are possible if the sets X_v are sparse: our main algorithmic result shows that if every vertex has at most x forbidden degrees (we call this special case AntiFactor_x), then the problem can be solved in time (x+1)^{O(tw)}⋅n^{O(1)}. That is, AntiFactor_x is fixed-parameter tractable parameterized by treewidth tw and the maximum number x of excluded degrees.
Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor₁ is already #W[1]-hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set X, we denote by X-AntiFactor the special case where every vertex v has the same set X_v = X of forbidden degrees. We show the following lower bound for every fixed set X: if there is an ε > 0 such that #X-AntiFactor can be solved in time (max X+2-ε)^{tw}⋅n^{O(1)} given a tree decomposition of width tw, then the Counting Strong Exponential-Time Hypothesis (#SETH) fails.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Anti-Factor
  • General Factor
  • Treewidth
  • Representative Sets
  • SETH

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized complexity of conflict-free matchings and paths. Algorithmica, 82(7):1939-1965, 2020. URL: https://doi.org/10.1007/s00453-020-00681-y.
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  3. Hans L Bodlaender. Dynamic programming on graphs with bounded treewidth. In International Colloquium on Automata, Languages, and Programming, pages 105-118. Springer, 1988. Google Scholar
  4. Hans L Bodlaender. Treewidth: Algorithmic techniques and results. In International Symposium on Mathematical Foundations of Computer Science, pages 19-36. Springer, 1997. Google Scholar
  5. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  6. 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.
  7. Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized feedback vertex set problems on bounded-treewidth graphs: Chordality is the key to single-exponential parameterized algorithms. Algorithmica, 81(10):3890-3935, 2019. URL: https://doi.org/10.1007/s00453-019-00579-4.
  8. Jin-yi Cai, Sangxia Huang, and Pinyan Lu. From Holant to #CSP and back: Dichotomy for Holant^c problems. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, volume 6506 of Lecture Notes in Computer Science, pages 253-265. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17517-6_24.
  9. Jin-yi Cai, Pinyan Lu, and Mingji Xia. A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci., 412(23):2468-2485, 2011. URL: https://doi.org/10.1016/j.tcs.2010.10.039.
  10. 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.
  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, 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.
  13. Víctor Dalmau and Daniel K. Ford. Generalized satisfability with limited occurrences per variable: A study through delta-matroid parity. In Branislav Rovan and Peter Vojtás, editors, Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, volume 2747 of Lecture Notes in Computer Science, pages 358-367. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45138-9_30.
  14. 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.
  15. 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.
  16. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  17. Eduard Eiben and Iyad Kanj. A colored path problem and its applications. ACM Trans. Algorithms, 16(4):47:1-47:48, 2020. URL: https://doi.org/10.1145/3396573.
  18. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  19. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative families of product families. ACM Trans. Algorithms, 13(3):36:1-36:29, 2017. URL: https://doi.org/10.1145/3039243.
  20. Heng Guo and Pinyan Lu. On the complexity of holant problems. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 159-177. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.6.
  21. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  22. Sangxia Huang and Pinyan Lu. A dichotomy for real weighted holant problems. Comput. Complex., 25(1):255-304, 2016. URL: https://doi.org/10.1007/s00037-015-0118-3.
  23. 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.
  24. Michael Kowalczyk and Jin-Yi Cai. Holant problems for 3-regular graphs with complex edge functions. Theory Comput. Syst., 59(1):133-158, 2016. URL: https://doi.org/10.1007/s00224-016-9671-7.
  25. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. J. ACM, 67(3):16:1-16:50, 2020. URL: https://doi.org/10.1145/3390887.
  26. L. Lovász and M. D. Plummer. Matching Theory. North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. Google Scholar
  27. László Lovász. The factorization of graphs. II. Acta Mathematica Hungarica, 23(1-2):223-246, 1972. Google Scholar
  28. Pinyan Lu. Complexity dichotomies of counting problems. Electron. Colloquium Comput. Complex., 18:93, 2011. URL: http://eccc.hpi-web.de/report/2011/093. Google Scholar
  29. Dániel Marx, Govind S. Sankar, and Philipp Schepper. Anti-factor is FPT parameterized by treewidth and list size (but counting is hard). CoRR, abs/2110.09369, 2021. URL: http://arxiv.org/abs/2110.09369.
  30. 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 Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 95:1-95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Full version: http://arxiv.org/abs/2105.08980. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.95.
  31. Dániel Marx and Paul Wollan. An exact characterization of tractable demand patterns for maximum disjoint path problems. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 642-661. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.44.
  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. Burkhard Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. Google Scholar
  34. András Sebö. General antifactors of graphs. J. Comb. Theory, Ser. B, 58(2):174-184, 1993. Google Scholar
  35. Hadas Shachnai and Meirav Zehavi. Representative families: A unified tradeoff-based approach. J. Comput. Syst. Sci., 82(3):488-502, 2016. URL: https://doi.org/10.1016/j.jcss.2015.11.008.
  36. 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.
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