We are given a directed graph $G(V, A)$ where each arc has a non-negative arc cost. We are given a set S, where each element of S contains a pair of $0$ cost arcs (both not already present in $G$). The task is to select 1 arc from each element of $S$ and add it to $G$ s.t. no SCC (strongly connected component) containing a positive arc exists in the resulting graph. The problem is to determine whether or not it is feasible to do so. Further, the number of elements in $S$ is polynomial in the number of vertices.
I am interested in establishing the complexity of determining feasibility. Does this remind anyone of a known problem which is either in $P$ or is $NP$-complete? If any of you have some ideas on how to approach this problem I would be very interested to see them.