# NP-complete reduction proof — graph problem

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.

• Observation: If each edge $v_1,v_2$ is considered to be a node in some new graph and an edge exists between $v_1,v_2$ and $v_3,v_4$ if they are both a pair in $S$ then the second constrant implies that the chosen subset of edges should be an independent set in this new graph. – Banach Tarski Mar 5 '16 at 7:56
• @Banach Tarski you are reducing OVERARCHING to IS. You have to do it other way round. – Shreesh Mar 5 '16 at 7:58
• I was trying to give a hint – Banach Tarski Mar 5 '16 at 8:00
• @Banach Your hint is more confusing then the solution. Anyway Independent set is set of vertices not edges. Independent edge set is nothing but maximal matching problem which is solvable in polynomial time. – Shreesh Mar 5 '16 at 8:02

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.