Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

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

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

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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.

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

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'

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

Experts Exchange Solution brought to you by

Your issues matter to us.

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

Start your 7-day free trialHowever, i still dont understand 1, could you be more precise, i think the answer is too vague !

Thanks

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

Math / Science

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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