Document Open Access Logo

Additive Sparsification of CSPs

Authors Eden Pelleg, Stanislav Živný

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.75.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Eden Pelleg
  • Mathematical Institute, University of Oxford, UK
Stanislav Živný
  • Department of Computer Science, University of Oxford, UK

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
  • Živný, Stanislav: Royal Society University Research Fellowship.

Cite AsGet BibTex

Eden Pelleg and Stanislav Živný. Additive Sparsification of CSPs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.75

Abstract

Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC'96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifiability of graphs with other 2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDMA'17] and non-Boolean domains by Butti and Živný [SIDMA'20]. Bansal, Svensson and Trevisan [FOCS'19] introduced a weaker notion of sparsification termed "additive sparsification", which does not require weights on the edges of the graph. In particular, Bansal et al. designed algorithms for additive sparsifiers for cuts in graphs and hypergraphs. As our main result, we establish that all Boolean Constraint Satisfaction Problems (CSPs) admit an additive sparsifier; that is, for every Boolean predicate P:{0,1}^k → {0,1} of a fixed arity k, we show that CSP(P)} admits an additive sparsifier. Under our newly introduced notion of all-but-one sparsification for non-Boolean predicates, we show that CSP(P)} admits an additive sparsifier for any predicate P:D^k → {0,1} of a fixed arity k on an arbitrary finite domain D.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Sparsification and spanners
Keywords
  • additive sparsification
  • graphs
  • hypergraphs
  • minimum cuts

Metrics

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

Related Versions

References

  1. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09), Part II, volume 5556 of Lecture Notes in Computer Science, pages 328-338. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02930-1_27.
  2. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. URL: https://doi.org/10.1137/S0097539796303421.
  3. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  4. Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang. On sketching quadratic forms. In Proceedings of the 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS'16), pages 311-–319. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840753.
  5. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, 1985. URL: https://doi.org/10.1145/4221.4227.
  6. Baruch Awerbuch, Yossi Azar, Avrim Blum, and Santosh S. Vempala. New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Comput., 28(1):254-262, 1998. URL: https://doi.org/10.1137/S009753979528826X.
  7. Nikhil Bansal, Ola Svensson, and Luca Trevisan. New notions and constructions of sparsification for graphs and hypergraphs. Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS'19), pages 910-928, 2019. URL: https://doi.org/10.1109/FOCS.2019.00059.
  8. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 672-681. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070526.
  9. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  10. Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM Review, 56(2):315-334, 2014. URL: https://doi.org/10.1137/130949117.
  11. András A. Benczúr and David R. Karger. Approximating s-t Minimum Cuts in Õ(n²) Time. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC'96), pages 47-55. ACM, 1996. URL: https://doi.org/10.1145/237814.237827.
  12. Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. SIAM J. Discret. Math., 19(4):1029-1055, 2005. URL: https://doi.org/10.1137/S0895480103431046.
  13. Richard A. Brualdi, Frank Harary, and Zevi Miller. Bigraphs versus digraphs via matrices. Journal of Graph Theory, 4(1):51-73, 1980. URL: https://doi.org/10.1002/jgt.3190040107.
  14. Silvia Butti and Stanislav Živný. Sparsification of binary CSPs. SIAM J. Discret. Math., 34(1):825-842, 2020. URL: https://doi.org/10.1137/19M1242446.
  15. Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P Liu, Richard Peng, Mark Sellke, and Daniel Vaz. Vertex sparsification for edge connectivity. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'21), 2021. URL: https://arxiv.org/abs/2007.07862.
  16. Shiri Chechik. New additive spanners. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pages 498-512. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.36.
  17. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput., 28(1):210-236, 1998. URL: https://doi.org/10.1137/S0097539794261295.
  18. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM J. Comput., 29(5):1740-1759, 2000. URL: https://doi.org/10.1137/S0097539797327908.
  19. Michael Elkin and Ofer Neiman. Near-additive spanners and near-exact hopsets, A unified view. Bull. EATCS, 130, 2020. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/608/624.
  20. Arnold Filtser and Robert Krauthgamer. Sparsification of two-variable valued constraint satisfaction problems. SIAM J. Discret. Math., 31(2):1263-1276, 2017. URL: https://doi.org/10.1137/15M1046186.
  21. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. SIAM J. Comput., 48(4):1196-1223, 2019. URL: https://doi.org/10.1137/16M1091666.
  22. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. URL: https://doi.org/10.1006/jcss.1998.1592.
  23. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 6th ACM Conference on Innovations in Theoretical Computer Science (ITCS'15), pages 367-376. ACM, 2015. URL: https://doi.org/10.1145/2688073.2688093.
  24. Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC'16), pages 842-850. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897640.
  25. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'2010), pages 47-56. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806698.
  26. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09), pages 3-12. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.28.
  27. Ilan Newman and Yuri Rabinovich. On multiplicative lambda-approximations and some geometric applications. SIAM J. Comput., 42(3):855-883, 2013. URL: https://doi.org/10.1137/100801809.
  28. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
  29. Eden Pelleg and Stanislav Živný. Additive Sparsification of CSPs, 2021. URL: http://arxiv.org/abs/2106.14757.
  30. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), volume 3580 of Lecture Notes in Computer Science, pages 261-272. Springer, 2005. URL: https://doi.org/10.1007/11523468_22.
  31. Tasuku Soma and Yuichi Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19), pages 2570-2581, 2019. URL: https://doi.org/10.1137/1.9781611975482.159.
  32. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913-1926, 2011. URL: https://doi.org/10.1137/080734029.
  33. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04), pages 81-90. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007372.
  34. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011. URL: https://doi.org/10.1137/08074489X.
  35. David P. Woodruff. Additive spanners in nearly quadratic time. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP'10), volume 6198 of Lecture Notes in Computer Science, pages 463-474. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_40.
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