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

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

###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
1. pick a set V' of k vertices,  for each pair of vertices in V' verify that the edge between them is in G

2. Given G =(V,E) we can construuct G' = (V, (V*V) - E) in O(|V|*|V|)

3. let (Vc,Ec) be a clique in G of size k, then (V-Vc,(V*V)-Ec) is a vertex cover of G'

4.let (Vv,Ev) be a vertex cover of G' of size |V|-k, then (V-Vv,(V*V)-Ev)
is a clique of size k
since for an pair of vertices (v1,v2) in V-Vv
Author Commented:
Hi
Thanks for your propmt response, i appreciate that
However, before i can grant you all the points. i need the following:

For 1: you need to provide a non-deterministic polynomial-time algorithm for the Clique Problem.

for 3: you need to specify the vertex cover (a set of vertices ONLY
- no edges!), and explain WHY it's a vertex cover.

for 4: you need to specify the clique (again, a set of vertices ONLY), and explain WHY it's a clique.

Hope you can do this and it will be just fine

Thanks

Commented:
1 nondeterministicly choose a set of k vertices,
In time O(k*k) verify that those vertices form a clique.
2 . Given G =(V,E) we can construuct G' = (V, (V*V) - E) in O(|V|*|V|)
3.
3. let (Vc,Ec) be a clique in G of size k,
then (V-Vc,(V*V)-Ec) is a vertex cover of G'
If [v1,v2] is an edge in G' then either v1 or v2 is a vertex in V-Vc
is not an element of V-Vc
(suppose neither v1 or v2 are elements of V-Vc, then v1 and v2 are
elements of Vc, and since  (Vc,Ec) is a clique,  [v1,v2] is an edge in Ec,
so [v1,v2] is not an edge in (V*V)-Ec

4 let Vv be a vertex cover of G' of size |V|-k, then (V-Vv.E) is a clique of size k
since for an pair of vertices v1,v2 in V-Vv the edge [v1,v2] is not in (V*V)-E, else Vv would not be a vertex cover of G'
Commented:
given G=(V,E), G`=(V,(V*V)-E)

S is a clique in G iff V-S is a vertex cover of G'

if S is a clique in G, then no edge in G' connects two verteces in S
so every edge in G' has at least one vertex in V-S so V-S is a vertex cover of G'

if V-S is a vertex cover of G', then every edge of G' has at least one vertex in V-S, so no edge of G' connects two vertices in S
so every pair of vertices of S is contained in G, so S is a clique in G
Commented:

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
However, i still dont understand 1, could you be more precise, i think the answer is too vague !

Thanks
Commented:
Did you look at the link I posted?
It proves the equivalence of
S is a clique of size k for G'
S is an independent set of size k for G
V-S is a vertex cover of size |V|-k for G
which might be easier to follow
Commented:
Is there any particular step ypu don't follow?
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.