Augmenting the Algebraic Connectivity of Graphs
Augmenting the Algebraic Connectivity of Graphs
复制标题
DOI：
10.4230/lipics.esa.2020.70
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Bogdan-Adrian Manghiuc;Pan Peng;He Sun
中科院分区：
文献类型：
--
作者：
Bogdan-Adrian Manghiuc;Pan Peng;He Sun
对于任意无向图G=（V，E）和一个候选边集E_W$，其中E\cap E_W=\emptyset$，$（k，\gamma）$-谱可扩充性问题是从E_W$中找到一个具有适当权值的k条边集F$，使得得到的图H=（V，E\cup F）$的代数连通度最小$\gamma$。由于代数连通性和许多其他图参数之间的紧密联系，包括图的电导和图中随机游动的混合时间，通过添加少量边来最大化所得到的图的代数连通性已经在过去的15年中进行了研究。在这项工作中，我们提出了一个近似的和有效的算法的$（k，\gamma）$-谱增广性问题，我们的算法运行在几乎线性的时间下的一个广泛的制度的参数。我们的主要算法是基于以下两个新的技术开发的文件中，这可能有应用程序以外的$（k，\gamma）$-谱扩充问题。(1)我们提出了一个快速算法，用于解决[GB 06]中代数连通性最大化问题的SDP的可行性版本。我们的算法是基于经典的原始-对偶框架求解SDP，这反过来又使用乘法的权重更新算法。提出了一种统一不同矩阵和向量变量的SDP约束的新方法，并给出了相应的分离预言。(2)我们提出了一个有效的子图稀疏化问题的算法，并为广泛的参数，我们的算法运行在几乎线性的时间，在以前最好的已知算法运行在至少$\Omega（n^2n）$时间[KMST 10]。我们的分析展示了如何在子图稀疏化的背景下推广随机BSS框架，以及如何应用势函数来近似跟踪不同的子空间。
For any undirected graph $G=(V,E)$ and a set $E_W$ of candidate edges with $E\cap E_W=\emptyset$, the $(k,\gamma)$-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\cup F)$ is least $\gamma$. 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. In this work we present an approximate and efficient algorithm for the $(k,\gamma)$-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,\gamma)$-spectral augmentability problem. (1) We present a fast algorithm for solving a feasibility version of an SDP for the algebraic connectivity maximisation problem from [GB06]. 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. (2) 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 $\Omega(n^2mk)$ time [KMST10]. 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.