Efficient Algorithms for Critical Node Detection on Path Graphs with Binary Connection Metrics

This paper investigates the Critical Node Detection Problem (CNDP) on path graphs where connection costs between node pairs are binary (0 or 1). Two variants of the problem are explored based on whether node weights are uniform or arbitrary. For both cases, the objective is to identify a subset of nodes whose removal minimizes the number of important connections surviving. Efficient dynamic programming algorithms are proposed to solve these problems optimally. When node weights are uniform, the approach runs in O(n³K) time, where n is the number of nodes and K is the maximum number of deletions allowed. For arbitrary node weights with a total removal budget W, the solution is derived in O(n⁵) time.