Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

NP Complete Problem: the clique and vertex cover !!

Posted on 2003-12-02
Medium Priority
1,194 Views
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

0
Question by:xdizen
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 6
• 2

LVL 84

Expert Comment

ID: 9860999
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
0

Author Comment

ID: 9861780
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

0

LVL 84

Expert Comment

ID: 9863787
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'
0

LVL 84

Expert Comment

ID: 9864280
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
0

LVL 84

Accepted Solution

ozo earned 2000 total points
ID: 9864473
0

Author Comment

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

Thanks
0

LVL 84

Expert Comment

ID: 9871813
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
0

LVL 84

Expert Comment

ID: 9936828
Is there any particular step ypu don't follow?
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses
Course of the Month5 days, 20 hours left to enroll