  We consider the consensus interdiction problem (CIP), in which the goal is to
maximize the convergence time of consensus averaging 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 source/sink edges, and
establish the same hardness result for the CIP. We then show that both ERIP and
CIP 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 iterative approximation algorithm to find a first-order stationary
solution for the CIP and evaluate its good performance through numerical
results.
