# Proof of NP-completeness via reduction

Tags:
1. Mar 4, 2016

### goraemon

1. The problem statement, all variables and given/known data
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 (a triangle, basically) would be described as follows: G = (V, E) = ({v1, v2, v3}, {v1v2, v2v3, v1v3}). A set S could consist of 0 or more pairs of G's edges. For example, a set S consisting of a single element could be simply {(v1v2, v2v3)}.

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.

Given a graph G, some subset of edge-pairs S, and some integer k >= 1, show that the problem of determining whether G contains a subset M of size at least k is NP-complete.

2. Relevant equations

Use reduction of a known NP-complete problem.

3. The attempt at a solution

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. Thanks for any assistance.

2. Mar 9, 2016