NP-complete reduction proof -- graph problem

Question

While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem:

You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs of $G$'s edges.

As an example, a complete graph on 3 vertices would be described as follows: $G = (V, E)$ = ({$v_1, v_2, v_3$}, {$v_1v_2, v_2v_3, v_1v_3$}). And you could be given a set $S$ which could consist of, say, two elements. E.g. $S$ = {$(v_1v_2, v_2v_3), (v_1v_2, v_1v_3)$}.

Now, we'll define $M$ as a subset of edges that has AT MOST one edge incident to each vertex in $G$, and AT MOST one edge from each pair in $S$. So for the example given above, $M$ could be any one of the following: {$v_1v_2$}, {$v_1v_3$}, or {$v_2v_3$}. $M$ cannot contain two (or more) edges for this example, though; if $M$ contained two edges, then there would be two edges that are incident to a single vertex in $G$, which is not allowed.

Here is the overarching problem statement: Given some graph $G$, some subset of edge-pairs $S$, and some integer $k >= 1$, determine whether $G$ contains a subset of edges, $M$, such that $|M| >= k$.

Your task: show that this problem is NP-complete.

I know I'm supposed to use reduction of a known NP-complete problem to show that the above problem is NP-complete, but I'm quite lost as to where to start, and even which known NP-complete problem to use for the reduction. Since it's a graph problem, I'm thinking perhaps something like vertex cover, independent set, clique, etc. might be used for reduction, but have no idea which or how. I also have a sneaking suspicion that some variant of 3-CNF SAT might be used here, but racking my brain hasn't helped thus far. Thank you for any assistance.

Answer 1

We can reduce independent set ($IS$) problem to the overarching ($OVERARCHING$) problem as follows. We reduce the instance $\langle G, k \rangle$ of IS to an instance $\langle G',S,k\rangle$ of OVERARCHING by the following reduction.

Each vertex $v_i \in V(G)$ becomes an edge $v^1_iv^2_i = e_{v_i} \in E(G')$. $G'$ will be a disconnected graph containing $|V(G)|$ edges and $2|V(G)|$ vertices. For every $v_iv_j \in E(G)$ we will add pair $(v^1_iv^2_i, v^1_jv^2_j) = (e_{v_i}, e_{v_j})$ in $S.$ If we select one of the vertices which are neighbor then we select one of the edge in the corresponding pair in the set $S$. Since all edges are disjoint in $G'$ we have absolute freedom there in selecting any edge we want.

Then $\langle G, k \rangle$ has a $k$-size independent set if and only if $\langle G',S,k\rangle$ has a $k$-size "overarching" set $M$.

Thus $IS \leq_P OVERARCHING$, and hence $OVERARCHING$ is NP-complete.