NP Complete Problem: the clique and vertex cover !!
Posted on 2003-12-02
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