Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index

摘要

The Kirchhoff index (𝒦_G), defined as the sum of effective resistances over all pairs of nodes in a connected undirected graph G, is a fundamental metric for real-world networks. It corresponds to average power consumption in electrical circuits, average commute time of random walks, and more relevantly to optimization, is equal to Tr(ℒ^†), where ℒ is the graph Laplacian. In this paper, we study the problem of augmenting a given graph by adding k edges to minimize the Kirchhoff index. The problem was introduced in a work of Ghosh, Boyd, and Saberi (2008), and is known to be NP-hard; the state-of-the-art algorithms mostly employ greedy heuristics and have very weak guarantees. We design novel algorithms and show bi-criteria approximation guarantees, i.e., the algorithm adds c · k edges and obtains an α factor approximation to the optimum objective value with k edges. Specifically, an algorithm based on k-median clustering with penalties achieves c=2 and α = O(k). By using known submodularity ideas, we extend this to achieve c=O(log k) and α=(4+ϵ). The problem corresponds to an augmentation version of the classic A-optimal experimental design problem in statistics. We also prove strong integrality gaps for the natural convex relaxation and demonstrate the performance of our algorithm on real and synthetic graphs.