Solved

NP Complete Problem: the clique and vertex cover !!

Posted on 2003-12-02
10
1,138 Views
Last Modified: 2007-12-19
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
Comment
Question by:xdizen
  • 6
  • 2
10 Comments
 
LVL 84

Expert Comment

by:ozo
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

by:xdizen
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

by:ozo
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

by:ozo
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 9864473
0
 

Author Comment

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

Thanks
0
 
LVL 84

Expert Comment

by:ozo
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

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

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Suggested Solutions

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now