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) adominating setof G is a subset V' of V such that for each vertex

vV \ V ' there exists a vertexv' V ' such that (v; v') E. Show that determining if G has a dominating set of size k is NP-complete.