graph problem

• (2 Pages)
• 1
• 2

16 Replies - 1276 Views - Last Post: 13 November 2016 - 09:58 AM

#1 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

graph problem

Posted 11 November 2016 - 02:31 PM

Let A be a algorithm with polynomial time, which receives a graph G and returns the stable set SA(G) of G with the property:
alpha(G) - |SA(G)| <= k for a constant k in N.
Prove that A can be used for determining , in polynomial time, a stable set of maximum cardinal in a given graph.
I have tried by taking K+1 isomorphic copies of the graph and I have tried to extend the graph. But I get stuck at this point, can you give me some help?

Is This A Good Question/Topic? 0

Replies To: graph problem

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 11 November 2016 - 08:09 PM

Let's do some algebra. What is \alpha((k+1)G), where (k+1)G denotes k+1 disjoint copies of G? Now run the algorithm A on (k+1)G, and select the vertices all belonging to the same copy of G from SA(G). Call this set S'. What can we say about \alpha(G) - |S'| ?

#3 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 01:32 AM

macosxnerd101, on 11 November 2016 - 08:09 PM, said:

Let's do some algebra. What is \alpha((k+1)G), where (k+1)G denotes k+1 disjoint copies of G? Now run the algorithm A on (k+1)G, and select the vertices all belonging to the same copy of G from SA(G). Call this set S'. What can we say about \alpha(G) - |S'| ?

\alpha((k+1)G) is the \alpha(G1) where G1 is the new graph. But I'm not sure how to do the second part (select vertices all belonging to the same copy from SA(G) ). Some help would be apreciated.

#4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 12 November 2016 - 09:16 AM

How does \alpha((k+1)G) relate to \alpha(G)?

And the vertices of the graph are labeled. So it should be easy to partition the vertices of SA((k+1)G) according to the component on which they belong. Keep in mind this is a high level algorithm.

#5 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 09:39 AM

macosxnerd101, on 12 November 2016 - 09:16 AM, said:

How does \alpha((k+1)G) relate to \alpha(G)?

And the vertices of the graph are labeled. So it should be easy to partition the vertices of SA((k+1)G) according to the component on which they belong. Keep in mind this is a high level algorithm.

\alpha((k+1)G) = \alpha(G) * (k+1).. And \alpha(G) - |S'| would be >= 0.

#6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 12 November 2016 - 09:42 AM

Quote

\alpha((k+1)G) = \alpha(G) * (k+1)

Yes. And in your proof, make sure you justify why.

Quote

And \alpha(G) - |S'| would be >= 0.

Are we interested in all the vertices from S'? Re-read my previous posts.

This post has been edited by macosxnerd101: 12 November 2016 - 11:17 AM
Reason for edit:: Ignore the bit about S'.

#7 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 10:03 AM

macosxnerd101, on 12 November 2016 - 09:42 AM, said:

Are we interested in all the vertices from S'? Re-read my previous posts.
[/quote]
Only the ones that are in SA(G) and belongs to the same copy of the graph. And... i got stuck .. How do i know which nodes are in SA(G).. SA(G) can be incomplete.

#8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 12 November 2016 - 10:07 AM

Claim: Let SA((k+1)G) be a stable set for (k+1)G. Then the vertices of SA((k+1)G) that belong to the same connected component of (k+1)G form a stable set of G.

Proof: An exercise for the reader.

#9 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 12:14 PM

Ok, so \alpha(G) - |SA(G)| <= k . How can I combine this information in order to prove the required sentence.

#10 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 12:22 PM

boob96, on 12 November 2016 - 12:14 PM, said:

Ok, so \alpha(G) - |SA(G)| <= k . How can I combine this information in order to prove the required sentence. />

\alpha(G) - |S'| <= k. Sorry

#11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 12 November 2016 - 12:51 PM

boob96, on 12 November 2016 - 02:14 PM, said:

Ok, so \alpha(G) - |SA(G)| <= k . How can I combine this information in order to prove the required sentence. />

That would be doing the work for you. As a small hint, can you construct a stable set of order \alpha(G) from SA((k+1)G)?

#12 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 12:57 PM

macosxnerd101, on 12 November 2016 - 12:51 PM, said:

boob96, on 12 November 2016 - 02:14 PM, said:

Ok, so \alpha(G) - |SA(G)| <= k . How can I combine this information in order to prove the required sentence. />/>

That would be doing the work for you. As a small hint, can you construct a stable set of order \alpha(G) from SA((k+1)G)?

If k is 0, yes.

#13 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 01:07 PM

So, |SG((K+1)G)| is also (K+1) * |SA(G)|. That reduces the problem to :
(k+1) * (\alpha(G) - |SA(G)|) <= k . => alpha(G) - |SA(G)| = 0 => alpha(G) = |SA(G)| which satisfies the condition.. Is that right?

#14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12134
• Posts: 45,114
• Joined: 27-December 08

Re: graph problem

Posted 12 November 2016 - 01:10 PM

Quote

So, |SG((K+1)G)| is also (K+1) * |SA(G)|

This would require proof. It's not obvious (contrary to what your intuition says).

In particular, this is not how I would approach the proof. I think otherwise, you are on the right track.

#15 boob96

Reputation: 0
• Posts: 9
• Joined: 11-November 16

Re: graph problem

Posted 12 November 2016 - 01:16 PM