An FPT algorithm for edge subset feedback edge set

Given a graph G=(V,E)G=(V,E) with a subset S⊆ES⊆E of edges, the edge subset feedback edge set problem is to find a smallest set F   of edges such that in G′=(V,E−F)G′=(V,E−F) no cycle contains an edge in S. We also define a restricted version of this problem, in which no edge in S is allowed to be selected into F   to form a solution. In this paper, we give a linear-time algorithm for the edge subset feedback edge set problem, and show that the restricted version is NP-hard for fixed |S|⩾2|S|⩾2 and fixed-parameter tractable with parameter being k=|F|k=|F|.

► The unweighted subset feedback edge set problem is linear-time solvable.
► The unweighted edge subset feedback edge set problem is linear-time solvable.
► The restricted edge subset feedback edge set problem is NP-hard and fixed-parameter tractable.