Consensus under Network Interruption and Effective Resistance Interdiction

We study the problem of network robustness under consensus dynamics. We first show that the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus dynamics subject to removing limited network edges, can be cast as an effective resistance interdiction problem (ERIP). We then show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges. We establish the same hardness result for the CIP, hence correcting some claims in the existing literature. We then show that both ERIP and CIP do not admit a polynomial-time approximation scheme, and moreover, they cannot be approximated up to a (nearly) polynomial factor assuming exponential time hypothesis. Finally, using a quadratic program formulation, we devise a polynomial-time $n^4$-approximation algorithm for ERIP that only depends on the number of nodes $n$ and is independent of the size of edge resistances. We also develop an iterative heuristic approximation algorithm to find a local optimum for the CIP.