Document Open Access Logo

Worst-Case to Expander-Case Reductions

Authors Amir Abboud , Nathan Wallheimer

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.1.pdf
  • Filesize: 0.85 MB
  • 23 pages

Document Identifiers

Author Details

Amir Abboud
  • Weizmann Institute of Science, Rehovot, Israel
Nathan Wallheimer
  • Weizmann Institute of Science, Rehovot, Israel

Funding

Supported by an Alon scholarship and a research grant from the Center for New Scientists at the Weizmann Institute of Science.

Acknowledgements

We thank the anonymous reviewers for their helpful comments that helped us improve the paper.

Cite AsGet BibTex

Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.1

Abstract

In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful hammer has led the community to (1) believe that most problems are as easy on worst-case graphs as they are on expanders, and (2) suspect that expander decompositions are the key to breaking the remaining longstanding barriers in fine-grained complexity. We set out to investigate the extent to which these two things are true (and for which problems). Towards this end, we put forth the concept of worst-case to expander-case self-reductions. We design a collection of such reductions for fundamental graph problems, verifying belief (1) for them. The list includes k-Clique, 4-Cycle, Maximum Cardinality Matching, Vertex-Cover, and Minimum Dominating Set. Interestingly, for most (but not all) of these problems the proof is via a simple gadget reduction, not via expander decompositions, showing that this hammer is effectively useless against the problem and contradicting (2).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Fine-Grained Complexity
  • Expander Decomposition
  • Reductions
  • Exact and Parameterized Complexity
  • Expander Graphs
  • Triangle
  • Maximum Matching
  • Clique
  • 4-Cycle
  • Vertex Cover
  • Dominating Set

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput., 47(6):2527-2555, 2018. URL: https://doi.org/10.1137/16M1061771.
  2. Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1487-1500. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520066.
  3. Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein. New hardness results for planar graph problems in P and an algorithm for sparsest cut. 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 996-1009. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384310.
  4. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477-486. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.58.
  5. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1681-1697. SIAM, 2014. Google Scholar
  6. Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Gomory-hu tree in subcubic time. arXiv preprint arXiv:2111.04958, 2021. Google Scholar
  7. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Subcubic algorithms for gomory-hu tree in unweighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1725-1737. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451073.
  8. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Friendly cut sparsifiers and faster Gomory-Hu trees. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3630-3649. SIAM, 2022. Google Scholar
  9. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  10. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. 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 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  11. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 239-252, 2018. Google Scholar
  12. Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander decomposition with fewer inter-cluster edges using a spectral cut player. CoRR, abs/2205.10301, 2022. URL: https://doi.org/10.48550/arXiv.2205.10301.
  13. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. arXiv preprint arXiv:1711.06530, 2017. Google Scholar
  14. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 522-539, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  15. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  16. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  17. Vahid R Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. arXiv preprint arXiv:2202.08996, 2022. Google Scholar
  18. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. 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 483-496. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055466.
  19. Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. Theory Comput., 8(1):69-94, 2012. URL: https://doi.org/10.4086/toc.2012.v008a004.
  20. Holger Bast, Kurt Mehlhorn, Guido Schafer, and Hisao Tamaki. Matching algorithms are fast in sparse random graphs. Theory of Computing Systems, 39(1):3-14, 2006. Google Scholar
  21. Richard Beigel. Finding maximum independent sets in sparse and general graphs. In SODA, volume 99, pages 856-857. Citeseer, 1999. Google Scholar
  22. Nicolas Bourgeois, Bruno Escoffier, Vangelis T Paschos, and Johan MM van Rooij. Fast algorithms for max independent set. Algorithmica, 62(1):382-415, 2012. Google Scholar
  23. Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. Near-optimal distributed triangle enumeration via expander decompositions. J. ACM, 68(3):21:1-21:36, 2021. URL: https://doi.org/10.1145/3446330.
  24. Jianer Chen, Iyad A Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In International symposium on mathematical foundations of computer science, pages 238-249. Springer, 2006. Google Scholar
  25. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. CoRR, abs/2203.00671, 2022. URL: https://doi.org/10.48550/arXiv.2203.00671.
  26. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1158-1167, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00111.
  27. Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 389-400. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316320.
  28. 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.
  29. Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. New techniques for proving fine-grained average-case hardness. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 774-785. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00077.
  30. Jacob Evald and Søren Dahlgaard. Tight hardness results for distance and centrality problems in constant degree graphs. CoRR, abs/1609.08403, 2016. URL: http://arxiv.org/abs/1609.08403.
  31. Fedor V Fomin, Fabrizio Grandoni, and Dieter Kratsch. Measure and conquer: A simple O(2^0.288n) independent set algorithm. In SODA, volume 6, pages 18-25. Citeseer, 2006. Google Scholar
  32. Fedor V Fomin, Dieter Kratsch, and Gerhard J Woeginger. Exact (exponential) algorithms for the dominating set problem. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 245-256. Springer, 2004. Google Scholar
  33. Oded Goldreich. Basic facts about expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 451-464. Springer, 2011. Google Scholar
  34. Monika Henzinger, Andrea Lincoln, and Barna Saha. The complexity of average-case dynamic subgraph counting. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 459-498. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.23.
  35. Monika Henzinger, Ami Paz, and AR Sricharan. Fine-grained complexity lower bounds for families of dynamic graphs. arXiv preprint arXiv:2208.07572, 2022. Google Scholar
  36. Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):497-515, 2004. URL: https://doi.org/10.1145/990308.990313.
  37. Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 217-226. SIAM, 2014. Google Scholar
  38. Alexander S. Kulikov and Ivan Mihajlin. Polynomial formulations as a barrier for reduction-based hardness proofs. CoRR, abs/2205.07709, 2022. URL: https://doi.org/10.48550/arXiv.2205.07709.
  39. Jason Li and Thatchaphol Saranurak. Deterministic weighted expander decomposition in almost-linear time. CoRR, abs/2106.01567, 2021. URL: http://arxiv.org/abs/2106.01567.
  40. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.80.
  41. Yaowei Long and Thatchaphol Saranurak. Near-optimal deterministic vertex-failure connectivity oracles. CoRR, abs/2205.03930, 2022. URL: https://doi.org/10.48550/arXiv.2205.03930.
  42. Silvio Micali and Vijay V. Vazirani. An O(√|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.
  43. Rajeev Motwani. Average-case analysis of algorithms for matchings and related problems. Journal of the ACM (JACM), 41(6):1329-1356, 1994. Google Scholar
  44. Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 248-255. IEEE, 2004. Google Scholar
  45. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 950-961. IEEE, 2017. Google Scholar
  46. Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the Lanczos method and an Õ(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 1141-1160, 2012. URL: https://doi.org/10.1145/2213977.2214080.
  47. Lorenzo Orecchia and Nisheeth K Vishnoi. Towards an SDP-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 532-545. SIAM, 2011. Google Scholar
  48. Igor Razgon. Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. Journal of Discrete Algorithms, 7(2):191-212, 2009. Google Scholar
  49. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2616-2635, 2019. URL: https://doi.org/10.1137/1.9781611975482.162.
  50. Daniel A Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, 42(1):1-26, 2013. Google Scholar
  51. Daniel A Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35(3):835-885, 2014. Google Scholar
  52. Johan MM Van Rooij and Hans L Bodlaender. Exact algorithms for dominating set. Discrete Applied Mathematics, 159(17):2147-2164, 2011. Google Scholar
  53. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3447-3487. World Scientific, 2018. Google Scholar
  54. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  55. Gerhard J Woeginger. Exact algorithms for NP-hard problems: A survey. In Combinatorial optimization—eureka, you shrink!, pages 185-207. Springer, 2003. Google Scholar
  56. Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM J. Discret. Math., 10(2):209-222, 1997. The conference version appeared in ICALP 1994. URL: https://doi.org/10.1137/S0895480194274133.
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