Document Open Access Logo

Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT

Authors Omer Wasim , Valerie King

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.33.pdf
  • Filesize: 0.53 MB
  • 19 pages

Document Identifiers

Author Details

Omer Wasim
  • Khoury College of Computer Sciences, Northeastern University, Boston, MA, USA
Valerie King
  • Department of Computer Science, University of Victoria, Canada

Funding

This research was completed while the first author was a MSc candidate at the University of Victoria. Both authors were funded by a NSERC Discovery Grant.

Acknowledgements

The authors thank Hung Le for useful discussions and an anonymous reviewer for helpful comments.

Cite As Get BibTex

Omer Wasim and Valerie King. Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.33

Abstract

This paper initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph G = (V,E), we present deterministic fully dynamic distributed and sequential algorithms to maintain a cut on G which always contains at least |E|/2 edges in sublinear update time under edge insertions and deletions to G. Our results include the following deterministic algorithms: i) an O(Δ) worst-case update time sequential algorithm, where Δ denotes the maximum degree of G, ii) the first fully dynamic distributed algorithm taking O(1) rounds and O(Δ) total bits of communication per update in the Massively Parallel Computation (MPC) model with n machines and O(n) words of memory per machine. The aforementioned algorithms require at most one adjustment, that is, a move of one vertex from one side of the cut to the other.
We also give the following fully dynamic sequential algorithms: i) a deterministic O(m^{1/2}) amortized update time algorithm where m denotes the maximum number of edges in G during any sequence of updates and, ii) a randomized algorithm which takes Õ(n^{2/3}) worst-case update time when edge updates come from an oblivious adversary.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Design and analysis of algorithms
Keywords
  • data structures
  • dynamic graph algorithms
  • approximate maximum cut
  • distributed computing
  • parallel computing

Metrics

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

References

  1. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 574–583, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591805.
  2. Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2):12:1-12:35, May 2016. URL: https://doi.org/10.1145/2837020.
  3. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 815-826, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188922.
  4. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1919-1936, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3310435.3310551.
  5. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in o (log n) update time. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 383-392, October 2011. URL: https://doi.org/10.1109/FOCS.2011.89.
  6. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’13, page 273–284, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2463664.2465224.
  7. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. 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 1899-1918. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.115.
  8. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. 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 1-20. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.1.
  9. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Dynamic algorithms via the primal-dual method. Inf. Comput., 261(Part):219-239, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.005.
  10. Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. Optimal dynamic distributed mis. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, page 217–226, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2933057.2933083.
  11. Keren Censor-Hillel, Rina Levy, and Hadas Shachnai. Fast distributed approximation for max-cut. In Antonio Fernández Anta, Tomasz Jurdzinski, Miguel A. Mosteiro, and Yanyong Zhang, editors, Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, volume 10718 of Lecture Notes in Computer Science, pages 41-56. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-72751-6_4.
  12. K. C. Chang and D. H. . Du. Efficient algorithms for layer assignment problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(1):67-78, 1987. Google Scholar
  13. Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, page 54–60, USA, 2004. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2004.39.
  14. Kwan-Wu Chin, Sieteng Soh, and Chen Meng. Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks. Computer Networks, 56:1200–1214, March 2012. URL: https://doi.org/10.1016/j.comnet.2011.12.001.
  15. 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, 2019. URL: http://arxiv.org/abs/1910.08025.
  16. Atish Das Sarma, Anisur Rahaman Molla, and Gopal Pandurangan. Distributed computation in dynamic networks via random walks. Theor. Comput. Sci., 581(C):45–66, May 2015. URL: https://doi.org/10.1016/j.tcs.2015.02.044.
  17. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107–113, January 2008. URL: https://doi.org/10.1145/1327452.1327492.
  18. Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. Parallel batch-dynamic graphs: Algorithms and lower bounds. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 1300–1319, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  19. Michel X. Goemans and David P. Williamson. .879-approximation algorithms for MAX CUT and MAX 2sat. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 422-431, 1994. URL: https://doi.org/10.1145/195058.195216.
  20. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Proceedings of the 22nd International Conference on Algorithms and Computation, ISAAC’11, page 374–383, Berlin, Heidelberg, 2011. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  21. Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A tree structure for dynamic facility location. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 39:1-39:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.39.
  22. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. 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 537-550. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055493.
  23. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set and other problems. CoRR, abs/1804.01823, 2018. URL: http://arxiv.org/abs/1804.01823.
  24. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. URL: https://doi.org/10.1145/320211.320215.
  25. Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis, and David Saulpic. Dominating sets and connected dominating sets in dynamic graphs. In STACS, 2019. Google Scholar
  26. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48:723-760, July 2001. URL: https://doi.org/10.1145/276698.276715.
  27. Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, and Nikos Parotsidis. Dynamic algorithms for the massively parallel computation model. In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’19, page 49–58, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3323165.3323202.
  28. David S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9(3):256-278, December 1974. URL: https://doi.org/10.1016/S0022-0000(74)80044-9.
  29. Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut using random walks. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 367-388. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/20.html.
  30. Bruce Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1131-1142, January 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  31. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, page 938–948, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  32. Richard M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming, 1972. Google Scholar
  33. Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Deterministic worst case dynamic connectivity: Simpler and faster. CoRR, abs/1507.05944, 2015. URL: http://arxiv.org/abs/1507.05944.
  34. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 146-154, 2004. URL: https://doi.org/10.1109/FOCS.2004.49.
  35. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput., 37(1):319–357, April 2007. URL: https://doi.org/10.1137/S0097539705447372.
  36. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 513–522, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806760.
  37. M. Luby. Removing randomness in parallel computation without a processor penalty. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 162-173, 1988. Google Scholar
  38. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms, 12(1):7:1-7:15, 2016. URL: https://doi.org/10.1145/2700206.
  39. Krzysztof Nowicki and Krzysztof Onak. Dynamic graph algorithms with batch updates in the massively parallel computation model, 2020. URL: http://arxiv.org/abs/2002.07800.
  40. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 457-464. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806753.
  41. M. Preissmann and Andras Sebo. Optimal cuts in graphs and statistical mechanics. Mathematical and Computer Modelling - MATH COMPUT MODELLING, 26:1-11, October 1997. URL: https://doi.org/10.1016/S0895-7177(97)00195-7.
  42. Yossi Shiloach and Shimon Even. An on-line edge-deletion problem. J. ACM, 28(1):1-4, January 1981. URL: https://doi.org/10.1145/322234.322235.
  43. Shay Solomon. Fully dynamic maximal matching in constant update time. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 325-334, 2016. Google Scholar
  44. José A. Soto. Improved analysis of a max-cut algorithm based on spectral partitioning. SIAM J. Discret. Math., 29(1):259-268, 2015. URL: https://doi.org/10.1137/14099098X.
  45. Mikkel Thorup. Fully-dynamic min-cut. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 224-230, 2001. URL: https://doi.org/10.1145/380752.380804.
  46. L. Trevisan. Max cut and the smallest eigenvalue. SIAM Journal on Computing, 41(6):1769-1786, 2012. URL: https://doi.org/10.1137/090773714.
  47. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time, 2016. URL: http://arxiv.org/abs/1611.02864.
  48. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, page 10, USA, 2010. USENIX Association. 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 About DROPS Imprint Privacy Contact