TDB: Breaking All Hop-Constrained Cycles in Billion-Scale Directed Graphs

The feedback vertex set is one of 21 Np-complete problems proposed by Karp, aiming at breaking all cycles in a given graph. It could be used in numerous areas, e.g., program analysis, database systems. In reality, users are concerned the cycles with constraints, e.g., the cycles with a hop constraint. For instance, in the E-commerce networks, the fraud detection team would discard cycles with a high number of hops since they are less relevant and grow exponentially in size. Thus, it is quite reasonable to investigate the feedback vertex set problem with hop-constrained cycles, namely hop-constrained cycle cover problem. It is concerned with determining a vertex set that covers all hop-constrained cycles in a given directed graph. A common method is to use a bottom-up algorithm, where it iteratively selects cover vertices into the result set. Based on this paradigm, the existing works mainly focus on the vertices orders and several heuristic strategies. In this paper, a totally opposite cover process top-down is proposed and bounds are presented on it. Surprisingly, both theoretical and practical performance are improved. On the theoretical side, this work is the first to achieve O(k•n•m) time complexity, whereas the state-of-the-art method achieves time complexity of O(n
^k
).
¹
On the practical level, the proposed algorithm, namely TDB++, outperforms the state-of-the-art by 2 to 3 orders of magnitude on average while preserving the minimal property. As a result, the method in this paper outperforms the state-of-the-art approaches in terms of both running time and theoretical time complexity. The hop-constrained cycle cover problem on billion-scale networks has been solved with a minimal
²
cover set for k > 3.