# Homework Help: 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

### Staff: Admin

Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted