Results 1 to 2 of 2

Math Help - Proving problem is NP-complete

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    23

    Proving problem is NP-complete

    Hey Im trying to prove that these problems are NP complete.

    Im trying to map them all to the Travelling Salesman problem.



     Dense subgraph Problem
    Input: A graph G, and integers k and t.
    Output: Does G contain a subgraph with exactly k vertices and at least t edges?

    Clique, no-clique Problem

    Input: An undirected graph G = (V;E) and an integer k.
    Output: Does G contain both a clique of size k and an independent set of size k.


    Dominating Set Problem
    Given a graph G = (V,E) a dominating set of G is a subset V' of  V such that for each vertex
    v \in V \ V ' there exists a vertex v' \in V ' such that (v; v') \in E. Show that determining if G has a dominating set of size k is NP-complete.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779
    Quote Originally Posted by DeRSeD View Post
    Im trying to map them all to the Travelling Salesman problem.
    It makes sense to reduce Traveling Salesman problem to these problems, not the other way around.

    Quote Originally Posted by DeRSeD View Post
    Dense subgraph Problem
    Input: A graph G, and integers k and t.
    Output: Does G contain a subgraph with exactly k vertices and at least t edges?
    This problem is more general than Clique.

    Quote Originally Posted by DeRSeD View Post
    Clique, no-clique Problem

    Input: An undirected graph G = (V;E) and an integer k.
    Output: Does G contain both a clique of size k and an independent set of size k.
    Reduce Clique to it: given a graph G, add k isolated points. Then there is an independent set of size k, and the question is only about a clique.


    Quote Originally Posted by DeRSeD View Post
    Dominating Set Problem
    Given a graph G = (V,E) a dominating set of G is a subset V' of V such that for each vertex
    v \in V \ V ' there exists a vertex v' \in V ' such that (v; v') \in E. Show that determining if G has a dominating set of size k is NP-complete.
    This I don't know immediately, but it is a well-known problem, so try searching the web. If you still can't find the solution, let us know again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 01:13 PM
  2. solve for x? help me complete the problem? :D
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 12th 2010, 10:36 AM
  3. Replies: 0
    Last Post: December 12th 2009, 12:15 AM
  4. complete induction problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 20th 2008, 11:48 AM
  5. [SOLVED] hi..NP complete problem...Urgent..
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 16th 2007, 06:37 PM

Search Tags


/mathhelpforum @mathhelpforum