🚀 go-pugleaf

I need to know whether the following problem is 
NP-complete. Seems like that to me - but I can 
not prove it.
-----------------------------------------------
Given an undirected unweighted graph (V,E) and
given a subset R of V, delete the minimum number
of edges so that all cycles involving at least 1
node from R are deleted. That is, in the final
solution, there may be cycles remaining in the
graph, but none involving nodes from R.

When R=V, this is equivalent to finding the
spanning tree of the graph and take the edge
complement of it. This kills all the cycles in 
the graph. 

When R={a} for some node a, it is equivalent to
deleting d(a) - 1 adjacent incident edges of a,
where d(a) is the degree of a. This kills all the
cycles through a.

So the two extremes are P, but what about in the
middle?

Any suggestions?

Thanks,
Apra.
----------------------------------------------------------------------------------
Apratim Sarkar 	    	      	   	     	       fone  (401)-863-7667 (off)    
Brown University, Box 1910     	   	     	       	     (617)-262-5515 (home)
Department of Computer Science	   	     	       fax   (401)-863-7657