1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof of NP-completeness via reduction

  1. Mar 4, 2016 #1
    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. jcsd
  3. Mar 9, 2016 #2
    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