Document Open Access Logo

Augmenting the Algebraic Connectivity of Graphs

Authors Bogdan-Adrian Manghiuc, Pan Peng , He Sun

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.70.pdf
  • Filesize: 0.67 MB
  • 22 pages

Document Identifiers

Author Details

Bogdan-Adrian Manghiuc
  • School of Informatics, University of Edinburgh, UK
Pan Peng
  • Department of Computer Science, University of Sheffield, UK
He Sun
  • School of Informatics, University of Edinburgh, UK

Funding

  • Sun, He: Support by an EPSRC Early Career Fellowship (EP/T00729X/1).

Cite AsGet BibTex

Bogdan-Adrian Manghiuc, Pan Peng, and He Sun. Augmenting the Algebraic Connectivity of Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 70:1-70:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.70

Abstract

For any undirected graph G = (V,E) and a set E_W of candidate edges with E ∩ E_W = ∅, the (k,γ)-spectral augmentability problem is to find a set F of k edges from E_W with appropriate weighting, such that the algebraic connectivity of the resulting graph H = (V, E ∪ F) is least γ. Because of a tight connection between the algebraic connectivity and many other graph parameters, including the graph’s conductance and the mixing time of random walks in a graph, maximising the resulting graph’s algebraic connectivity by adding a small number of edges has been studied over the past 15 years, and has many practical applications in network optimisation. In this work we present an approximate and efficient algorithm for the (k,γ)-spectral augmentability problem, and our algorithm runs in almost-linear time under a wide regime of parameters. Our main algorithm is based on the following two novel techniques developed in the paper, which might have applications beyond the (k,γ)-spectral augmentability problem: - We present a fast algorithm for solving a feasibility version of an SDP for the algebraic connectivity maximisation problem from [Ghosh and Boyd, 2006]. Our algorithm is based on the classic primal-dual framework for solving SDP, which in turn uses the multiplicative weight update algorithm. We present a novel approach of unifying SDP constraints of different matrix and vector variables and give a good separation oracle accordingly. - We present an efficient algorithm for the subgraph sparsification problem, and for a wide range of parameters our algorithm runs in almost-linear time, in contrast to the previously best known algorithm running in at least Ω(n²mk) time [Kolla et al., 2010]. Our analysis shows how the randomised BSS framework can be generalised in the setting of subgraph sparsification, and how the potential functions can be applied to approximately keep track of different subspaces.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Graph sparsification
  • Algebraic connectivity
  • Semidefinite programming

Metrics

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

Related Versions

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS'16), pages 335-344, 2016. Google Scholar
  2. Zeyuan Allen-Zhu and Yuanzhi Li. Doubly accelerated methods for faster CCA and generalized eigendecomposition. In 34th International Conference on Machine Learning (ICML'17), pages 98-106, 2017. Google Scholar
  3. Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal design of experiments via regret minimization. In 34th International Conference on Machine Learning (ICML'17), pages 126-135, 2017. Google Scholar
  4. Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond multiplicative updates. In 47th Annual ACM Symposium on Theory of Computing (STOC'15), pages 237-245, 2015. Google Scholar
  5. Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM, 63(2):12, 2016. Google Scholar
  6. Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704-1721, 2012. Google Scholar
  7. Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing Markov chain on a graph. SIAM review, 46(4):667-689, 2004. Google Scholar
  8. Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna. Network design for vertex connectivity. In 40th Annual ACM Symposium on Theory of Computing (STOC'08), pages 167-176, 2008. Google Scholar
  9. Joseph Cheriyan and László A Végh. Approximating minimum-cost k-node connected subgraphs via independence-free graphs. SIAM Journal on Computing, 43(4):1342-1362, 2014. Google Scholar
  10. Julia Chuzhoy and Sanjeev Khanna. An O(k³ log n)-approximation algorithm for vertex-connectivity survivable network design. In 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09), pages 437-441, 2009. Google Scholar
  11. Michael B. Cohen, Jelani Nelson, and David P. Woodruff. Optimal approximate matrix product in terms of stable rank. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16), pages 1-14, 2016. Google Scholar
  12. Michael Dinitz and Zeyu Zhang. Approximating low-stretch spanners. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), pages 821-840, 2016. Google Scholar
  13. Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 750-759, 1999. Google Scholar
  14. Jittat Fakcharoenphol and Bundit Laekhanukit. An O(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem. SIAM Journal on Computing, 41(5):1095-1109, 2012. Google Scholar
  15. Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298-305, 1973. Google Scholar
  16. Arpita Ghosh and Stephen Boyd. Growing well-connected graphs. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 6605-6611, 2006. Google Scholar
  17. Arpita Ghosh, Stephen Boyd, and Amin Saberi. Minimizing effective resistance of a graph. SIAM review, 50(1):37-66, 2008. Google Scholar
  18. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In 26th Annual ACM Symposium on Theory of Computing (STOC'94), pages 356-364, 1994. Google Scholar
  19. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP= PSPACE. Journal of the ACM (JACM), 58(6):30, 2011. Google Scholar
  20. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM Journal on Computing, 46(1):456-477, 2017. Google Scholar
  21. Jonathan A Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory of Computing Systems, 53(2):243-262, 2013. Google Scholar
  22. Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shang-Hua Teng. Subgraph sparsification and nearly optimal ultrasparsifiers. In 42nd Annual ACM Symposium on Theory of Computing (STOC'10), pages 57-66, 2010. Google Scholar
  23. Guy Kortsarz, Robert Krauthgamer, and James R Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM Journal on Computing, 33(3):704-720, 2004. Google Scholar
  24. Bundit Laekhanukit. Parameters of two-prover-one-round game and the hardness of connectivity problems. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 1626-1643, 2014. Google Scholar
  25. Yin Tat Lee and He Sun. An SDP-based algorithm for linear-sized spectral sparsification. In 49th Annual ACM Symposium on Theory of Computing (STOC'17), pages 678-687, 2017. Google Scholar
  26. Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 47(6):2315-2336, 2018. Google Scholar
  27. Marina Meila and Jianbo Shi. Learning segmentation by random walks. In Advances in Neural Information Processing Systems, pages 873-879, 2001. Google Scholar
  28. William M Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness, Alex C Snoeren, and George Porter. Expanding across time to deliver bandwidth efficiency and low latency. Proceedings of the 17th ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2020. Google Scholar
  29. Milena Mihail. Conductance and convergence of Markov chains-a combinatorial treatment of expanders. In 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS'89), pages 526-531, 1989. Google Scholar
  30. Damon Mosk-Aoyama. Maximum algebraic connectivity augmentation is NP-hard. Operations Research Letters, 36(6):677-679, 2008. Google Scholar
  31. Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849-856, 2002. Google Scholar
  32. Aleksandar Nikolov, Mohit Singh, and Uthaipon Tao Tantipongpipat. Proportional volume sampling and approximation algorithms for a-optimal design. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19), pages 1369-1386, 2019. Google Scholar
  33. 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 22th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11), pages 532-545, 2011. Google Scholar
  34. Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 1256-1266, 2014. URL: https://doi.org/10.1137/1.9781611973402.93.
  35. Richard Peng. Algorithm Design Using Spectral Graph Theory. PhD Thesis, 2013. URL: https://doi.org/10.1184/R1/6714635.v1.
  36. Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! SIAM Journal on Computing, 46(2):710-743, 2017. Google Scholar
  37. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput., 82(1):93-133, 1989. Google Scholar
  38. Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Information Theory, 42(6):1710-1722, 1996. Google Scholar
  39. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  40. Leslie G. Valiant. Graph-theoretic properties in computational complexity. J. Comput. Syst. Sci., 13(3):278-285, 1976. Google Scholar
  41. Nisheeth K. Vishnoi. Lx = b. Foundations and Trends in Theoretical Computer Science, 8(1-2):1-141, 2013. Google Scholar
  42. Gilles Zémor. On expander codes. IEEE Trans. Information Theory, 47(2):835-837, 2001. 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