Document Open Access Logo

Minimum Stable Cut and Treewidth

Author Michael Lampis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.92.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Michael Lampis
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France

Funding

The author is supported by ANR JCJC project "ASSK" (ANR-18-CE40-0025-01).

Acknowledgements

Part of this work was conducted while the author was on sabbatical at IRIF, UMR 8243, Université de Paris.

Cite AsGet BibTex

Michael Lampis. Minimum Stable Cut and Treewidth. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 92:1-92:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.92

Abstract

A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. Equivalently, a cut is stable if all vertices have the (weighted) majority of their neighbors on the other side. Finding a stable cut is a prototypical PLS-complete problem that has been studied in the context of local search and of algorithmic game theory. In this paper we study Min Stable Cut, the problem of finding a stable cut of minimum weight, which is closely related to the Price of Anarchy of the Max Cut game. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudo-polynomial DP algorithm solving the problem in time (Δ⋅ W)^{O(tw)}n^{O(1)}, where tw is the treewidth, Δ the maximum degree, and W the maximum weight. On the other hand, bounding Δ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Min Stable Cut by both tw and Δ and obtain an FPT algorithm running in time 2^{O(Δtw)}(n+log W)^{O(1)}. Our main result for the weighted problem is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in (nW)^{o(pw)} or 2^{o(Δpw)}(n+log W)^{O(1)}, then the ETH is false. Complementing this, we show that we can, however, obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions, that is, solutions where no single vertex can unilaterally increase the weight of its incident cut edges by more than a factor of (1+ε). Motivated by these mostly negative results, we consider Unweighted Min Stable Cut. Here our results already imply a much faster exact algorithm running in time Δ^{O(tw)}n^{O(1)}. We show that this is also probably essentially optimal: an algorithm running in n^{o(pw)} would contradict the ETH.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Treewidth
  • Local Max-Cut
  • Nash Stability

Metrics

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

Related Versions

References

  1. Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring & friends, half-graphs, bicliques. In STACS, volume 154 of LIPIcs, pages 58:1-58:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  2. Eric Angel, Evripidis Bampis, Bruno Escoffier, and Michael Lampis. Parameterized power vertex cover. Discret. Math. Theor. Comput. Sci., 20(2), 2018. URL: http://dmtcs.episciences.org/4873.
  3. Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 429-437. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055402.
  4. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven Skiena. The lazy bureaucrat scheduling problem. Inf. Comput., 184(1):129-146, 2003. Google Scholar
  5. Per Austrin, Mark Braverman, and Eden Chlamtac. Inapproximability of NP-complete variants of Nash equilibrium. Theory Comput., 9:117-142, 2013. URL: https://doi.org/10.4086/toc.2013.v009a003.
  6. Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, and Alexander Skopalik. Fast convergence to nearly optimal solutions in potential games. In Lance Fortnow, John Riedl, and Tuomas Sandholm, editors, Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008, pages 264-273. ACM, 2008. URL: https://doi.org/10.1145/1386790.1386832.
  7. Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. Improved equilibria via public service advertising. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 728-737. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496850.
  8. C. Bazgan, L. Brankovic, K. Casel, H. Fernau, K. Jansen, K.-M. Klein, M. Lampis, M. Liedloff, J. Monnot, and V. T. Paschos. The many facets of upper domination. Theoretical Computer Science, 717:2-25, 2018. Google Scholar
  9. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 14:1-14:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.14.
  10. Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring. SIAM J. Discret. Math., 34(2):1084-1106, 2020. URL: https://doi.org/10.1137/18M1223666.
  11. Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. In David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz, editors, Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010, pages 73-82. ACM, 2010. URL: https://doi.org/10.1145/1807342.1807353.
  12. Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran. Improving the smoothed complexity of FLIP for max cut problems. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 897-916. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.55.
  13. Vittorio Bilò and Marios Mavronicolas. The complexity of computational problems about Nash equilibria in symmetric win-lose games. CoRR, abs/1907.10468, 2019. URL: http://arxiv.org/abs/1907.10468.
  14. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. Google Scholar
  15. É. Bonnet, M. Lampis, and V. T. Paschos. Time-approximation trade-offs for inapproximable problems. Journal of Computer and System Sciences, 92:171-180, 2018. Google Scholar
  16. Mark Braverman, Young Kun-Ko, and Omri Weinstein. Approximating the best Nash equilibrium in n^o^(log n)-time breaks the exponential time hypothesis. 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 970-982. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.66.
  17. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Economics and Comput., 3(1):2:1-2:32, 2015. URL: https://doi.org/10.1145/2614687.
  18. Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang. Smoothed complexity of local max-cut and binary max-CSP. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1052-1065. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384325.
  19. George Christodoulou, Vahab S. Mirrokni, and Anastasios Sidiropoulos. Convergence and approximation in potential games. Theor. Comput. Sci., 438:13-27, 2012. URL: https://doi.org/10.1016/j.tcs.2012.02.033.
  20. Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games Econ. Behav., 63(2):621-641, 2008. URL: https://doi.org/10.1016/j.geb.2008.02.015.
  21. 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.
  22. Argyrios Deligkas, John Fearnley, and Rahul Savani. Inapproximability results for constrained approximate Nash equilibria. Inf. Comput., 262(Part):40-56, 2018. URL: https://doi.org/10.1016/j.ic.2018.06.001.
  23. Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (in)approximability of maximum minimal FVS. In ISAAC, volume 181 of LIPIcs, pages 3:1-3:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. Upper dominating set: Tight algorithms for pathwidth and sub-exponential approximation. CoRR, abs/2101.07550, 2021. URL: http://arxiv.org/abs/2101.07550.
  25. Edith Elkind, Leslie Ann Goldberg, and Paul W. Goldberg. Nash equilibria in graphical games on trees revisited. In Joan Feigenbaum, John C.-I. Chuang, and David M. Pennock, editors, Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), Ann Arbor, Michigan, USA, June 11-15, 2006, pages 100-109. ACM, 2006. URL: https://doi.org/10.1145/1134707.1134719.
  26. Edith Elkind, Leslie Ann Goldberg, and Paul W. Goldberg. Computing good nash equilibria in graphical games. In Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, pages 162-171. ACM, 2007. URL: https://doi.org/10.1145/1250910.1250935.
  27. Robert Elsässer and Tobias Tscheuschner. Settling the complexity of local max-cut (almost) completely. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, pages 171-182. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_15.
  28. Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In IPEC 2019, pages 13:1-13:15, 2019. Google Scholar
  29. Michael Etscheid and Heiko Röglin. Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms, 13(2):25:1-25:12, 2017. URL: https://doi.org/10.1145/3011870.
  30. Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 604-612. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007445.
  31. Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis. Node-max-cut and the complexity of equilibrium in linear weighted congestion games. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 50:1-50:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.50.
  32. Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul G. Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. Theor. Comput. Sci., 410(36):3305-3326, 2009. URL: https://doi.org/10.1016/j.tcs.2008.01.004.
  33. F. Furini, I. Ljubić, and M. Sinnl. An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem. European Journal of Operational Research, 262(2):438-448, 2017. Google Scholar
  34. Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989. Google Scholar
  35. Laurent Gourvès and Jérôme Monnot. On strong equilibria in the max cut game. In Stefano Leonardi, editor, Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, volume 5929 of Lecture Notes in Computer Science, pages 608-615. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10841-9_62.
  36. Laurent Gourvès, Jérôme Monnot, and Aris Pagourtzis. The lazy bureaucrat problem with common arrivals and deadlines: Approximation and mechanism design. In FCT, volume 8070 of Lecture Notes in Computer Science, pages 171-182. Springer, 2013. Google Scholar
  37. Gianluigi Greco and Francesco Scarcello. On the complexity of constrained Nash equilibria in graphical games. Theor. Comput. Sci., 410(38-40):3901-3924, 2009. URL: https://doi.org/10.1016/j.tcs.2009.05.030.
  38. Tesshu Hanaka, Hans L. Bodlaender, Tom C. van der Zanden, and Hirotaka Ono. On the maximum weight minimal separator. Theoretical Computer Science, 796:294-308, 2019. Google Scholar
  39. Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best Nash equilibrium? SIAM J. Comput., 40(1):79-91, 2011. URL: https://doi.org/10.1137/090766991.
  40. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  41. Ken Iwaide and Hiroshi Nagamochi. An improved algorithm for parameterized edge dominating set problem. J. Graph Algorithms Appl., 20(1):23-58, 2016. Google Scholar
  42. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. URL: https://doi.org/10.1016/0022-0000(88)90046-3.
  43. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math., 264:90-117, 2019. URL: https://doi.org/10.1016/j.dam.2018.11.002.
  44. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. Discrete Applied Mathematics, 2020. URL: https://doi.org/10.1016/j.dam.2020.03.052.
  45. Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, and Florian Sikora. Weighted upper edge cover: Complexity and approximability. J. Graph Algorithms Appl., 24(2):65-88, 2020. Google Scholar
  46. Michael Lampis. Parameterized approximation schemes using graph widths. 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 775-786. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_64.
  47. Michael Lampis and Valia Mitsou. Treewidth with a quantifier alternation revisited. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume 89 of LIPIcs, pages 26:1-26:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.26.
  48. Martin Loebl. Efficient maximal cubic graph cuts (extended abstract). In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez-Artalejo, editors, Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings, volume 510 of Lecture Notes in Computer Science, pages 351-362. Springer, 1991. URL: https://doi.org/10.1007/3-540-54233-7_147.
  49. Lorenz Minder and Dan Vilenchik. Small clique detection and approximate Nash equilibria. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 673-685. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_50.
  50. Dominik Peters. Graphical hedonic games of bounded treewidth. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 586-593. AAAI Press, 2016. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12400.
  51. Svatopluk Poljak. Integer linear programs and local search for max-cut. SIAM J. Comput., 24(4):822-839, 1995. URL: https://doi.org/10.1137/S0097539793245350.
  52. Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56-87, 1991. URL: https://doi.org/10.1137/0220004.
  53. Grant Schoenebeck and Salil P. Vadhan. The computational complexity of Nash equilibria in concisely represented games. ACM Trans. Comput. Theory, 4(2):4:1-4:50, 2012. URL: https://doi.org/10.1145/2189778.2189779.
  54. M. Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics, 31(4):2440-2456, 2017. 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 Imprint Privacy Contact