On the Non-Submodularity of the Problem of Adding Links to Minimize the Effective Graph Resistance

Abstract

We consider the optimisation problem of adding $k$ links to a given network, such that the resulting effective graph resistance is as small as possible.
The problem was recently proven to be NP-hard, such that obtaining optimal solutions through brute-force methods is infeasible for any graph of realistic size.
It is common in such cases to use a simple greedy algorithm to obtain an approximation of the optimal solution. It is known that if the considered problem is submodular, the quality of the greedy solution can be guaranteed.
However, the considered optimisation problem is known to be not submodular. For such cases one can use the notion of generalized submodularity, which is captured by the submodularity ratio $\gamma$.
A performance bound, which is a function of $\gamma$, also exists in case of generalized submodularity. In this paper we give an example of a family of graphs where the submodularity ratio approaches zero, implying that the solution quality of the greedy algorithm cannot be guaranteed through the concept of generalized submodularity, at least, according to the currently available theoretical results.
Finally, we conduct some numerical experiments on small graphs. Even though we lack a theory to guarantee the performance of the greedy algorithm, the experiments show that the greedy algorithm leads to near-optimal solutions.