Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index

The Kirchhoff index ($\mathcal{K}_{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 $\text{Tr}(\mathcal{L}^{\dagger})$, where $\mathcal{L}$ 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 \cdot k$ edges and obtains an $\alpha$ factor approximation to the optimum objective value with $k$ edges. Specifically, an algorithm based on $k$-median clustering with penalties achieves $c=2$ and $\alpha = O(k)$. By using known submodularity ideas, we extend this to achieve $c=O(\log k)$ and $\alpha=(4+\epsilon)$. 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.