# Proving problem is NP-complete

• May 12th 2011, 10:05 AM
DeRSeD
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.
• May 12th 2011, 11:47 AM
emakarov
Quote:

Originally Posted by DeRSeD
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
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
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
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.