| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427265 | Information Processing Letters | 2012 | 5 Pages |
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.
