graph problem

  • (2 Pages)
  • +
  • 1
  • 2

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

#1 boob96  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • 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'| ?
Was This Post Helpful? 1
  • +
  • -

#3 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 01:32 AM

View Postmacosxnerd101, 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. :wheelchair:
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 09:39 AM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • 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'.

Was This Post Helpful? 0
  • +
  • -

#7 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 10:03 AM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 boob96  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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. :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#10 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 12:22 PM

View Postboob96, 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. :bigsmile:/>

\alpha(G) - |S'| <= k. Sorry
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




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

Re: graph problem

Posted 12 November 2016 - 12:51 PM

View Postboob96, 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. :bigsmile:/>

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)?
Was This Post Helpful? 0
  • +
  • -

#12 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 12:57 PM

View Postmacosxnerd101, on 12 November 2016 - 12:51 PM, said:

View Postboob96, 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. :bigsmile:/>/>

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.
Was This Post Helpful? 0
  • +
  • -

#13 boob96  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#15 boob96  Icon User is offline

  • New D.I.C Head

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

Re: graph problem

Posted 12 November 2016 - 01:16 PM

But what is your approach?

This post has been edited by andrewsw: 12 November 2016 - 01:20 PM
Reason for edit:: Removed previous quote, just press REPLY

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2