Partial Feedback Edge Set

Input

Graph $G = (V, E)$ , positive integers $K \leq |E|$ and $L \leq |V|$ .

Question

Is there a subset $E' \subseteq E$ with $|E'| \leq K$ such that $E'$ contains at least one edge from every circuit of length $L$ or less in $G$ ?

Remains NP-complete for any fixed $L \geq 3$ and for bipartite graphs (with fixed $L \geq 4$ ). However, if $L = |V|$ , i.e. if we ask that $E'$ contains an edge from every cycle in $G$ , then the problem is trivially solvable in polynomial time.

Proofs

NP-complete

Transformation from Vertex Cover (Yannakakis, 1978).

Reducible from

Vertex Cover

References

Yannakakis, M. (1978). Node-and edge-deletion NP-complete problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804355