Search Results

Documents authored by Manghiuc, Bogdan-Adrian


Document
Augmenting the Algebraic Connectivity of Graphs

Authors: Bogdan-Adrian Manghiuc, Pan Peng, and He Sun

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{manghiuc_et_al:LIPIcs.ESA.2020.70,
  author =	{Manghiuc, Bogdan-Adrian and Peng, Pan and Sun, He},
  title =	{{Augmenting the Algebraic Connectivity of Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{70:1--70:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.70},
  URN =		{urn:nbn:de:0030-drops-129367},
  doi =		{10.4230/LIPIcs.ESA.2020.70},
  annote =	{Keywords: Graph sparsification, Algebraic connectivity, Semidefinite programming}
}
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