asked on

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

ozo

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

xdizen

ASKER

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

ozo

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'

ozo

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

ASKER CERTIFIED SOLUTION

ozo

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

xdizen

ASKER

Thanks for your posting
However, i still dont understand 1, could you be more precise, i think the answer is too vague !

Thanks

ozo

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

ozo

Is there any particular step ypu don't follow?