Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1204
  • Last Modified:

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


0
xdizen
Asked:
xdizen
  • 6
  • 2
1 Solution
 
ozoCommented:
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
 
xdizenAuthor 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



0
 
ozoCommented:
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
ozoCommented:
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
 
xdizenAuthor Commented:
Thanks for your posting
However, i still dont understand 1, could you be more precise, i think the answer is too vague !

Thanks
0
 
ozoCommented:
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
 
ozoCommented:
Is there any particular step ypu don't follow?
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 6
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now