Complexity of Maximizing Convergence Time in Network Consensus Dynamics Subject to Edge Removal

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