Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-006 (March 07, 2011)

An FPT Algorithm for Edge Subset Feedback Edge Set
by Mingyu Xiao and Hiroshi Nagamochi

pdf File

Given a graph $G=(V,E)$ with a subset $S\subseteq 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)$ no cycle contains an edge in $S$. We also define a restricted version of this problem, in which no edges 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 the restricted version is NP-hard for fixed $|S|\geq2$ and fixed-parameter tractable with parameter being $k=|F|$.