Solved

# NP Complete Problem: the clique and vertex cover !!

Posted on 2003-12-02

HI all

I am lost in this stuff and i need some help !

THE CLIQUE PROBLEM

Given an undirected graph G = (V,E) and an integer k, does g contain a complete subgraph of at leat k vertices ?

THE VERTEX COVER PROBLEM:

Given an undirected graph G = (V,E) and an integer k, does g contain a subset of vertices V' such that |V'| =< k and every edge in G has at least on endpoint V' ?

to anwer that, i need the following proof :

1. Proof that Clique problem is NP by specifying a nondeterministic polynomial time solution for it

2. I need a proof that Clique is polonomially reductible to the Vertex cover pb. use G =(V,E) and k instance of Clique pb, also use complementary graph G' = (V, (V*V) - E) and |V| - k as instance of Vertex problem

3. proof that if G has clique of size k, then G' has vertex cover of |V|-k

4.proof that if G' has vertex cover of |V|-k, then G has clique of size k

This is a complex question and therefore i put lots of point on it

Thanks to all