Scalable approximations to k-cycle transversal problems on dynamic networks

摘要

We study scalable approximation algorithms for the k-cycle transversal problem, which is to find a minimum-size set of edges that intersects all simple cycles of length k in a network. This problem is relevant to network reliability through the important metric of network clustering coefficient of order k. We formulate two algorithms to be both scalable and have good solution quality in practice: CARL and DARC. DARC is able to efficiently update its solution under dynamic node and edge insertion and removal to the network. In our experimental evaluation, we demonstrate that DARC is able to run on networks with billions of 3-cycles within 2 h and is able to dynamically update its solution in microseconds.