Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index

Prasanth Yalamanchili, Aditya Bhaskara
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3745-3753, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-yalamanchili26a, title = { Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index }, author = {Yalamanchili, Prasanth and Bhaskara, Aditya}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3745--3753}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/yalamanchili26a/yalamanchili26a.pdf}, url = {https://proceedings.mlr.press/v300/yalamanchili26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index %A Prasanth Yalamanchili %A Aditya Bhaskara %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-yalamanchili26a %I PMLR %P 3745--3753 %U https://proceedings.mlr.press/v300/yalamanchili26a.html %V 300 %X 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.
APA
Yalamanchili, P. & Bhaskara, A.. (2026). Clustering-Based Edge Augmentation for Minimizing the Kirchhoff Index . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3745-3753 Available from https://proceedings.mlr.press/v300/yalamanchili26a.html.

Related Material