NP-hardness proved for removing cycle patterns from graphs
NP-Hardness of the $H$-Free Edge-Deletion Problem
Computational Complexity
Summary
This paper studies how hard it is to delete the fewest edges from a network to ensure it does not contain a certain cycle pattern. The authors prove that whenever the forbidden pattern contains a cycle, the problem is NP-hard, meaning it is unlikely that an efficient algorithm exists to solve all cases quickly. This settles a previous question posed by other researchers and completes the understanding of which patterns cause computational difficulty in this problem. Their work clarifies precisely when the edge deletion problem becomes challenging based on the presence of cycles.
What this means in practice
- •For network engineers: Recognize when removing certain cycle patterns from network graphs cannot be efficiently computed due to inherent complexity limits.
- •For software developers: Understand which types of graph simplifications involving cycle removal are computationally infeasible to guide practical optimization choices.
A theory result. No direct application yet.
Authors
Lior Gishboliner, Ethan Honest
Abstract
For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.