Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal
研究了在移除有限数量网络边的情况下，如何最大化共识平均动力学的收敛时间，证明了该问题是强NP难且无法多项式近似，并提出了近似算法。
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 the 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 experiments.