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

### #1

# graph problem

Posted 11 November 2016 - 02:31 PM

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?

##
**Replies To:** graph problem

### #2

## Re: graph problem

Posted 11 November 2016 - 08:09 PM

### #3

## Re: graph problem

Posted 12 November 2016 - 01:32 AM

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

\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

## Re: graph problem

Posted 12 November 2016 - 09:16 AM

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

## Re: graph problem

Posted 12 November 2016 - 09:39 AM

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

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

## Re: graph problem

Posted 12 November 2016 - 09:42 AM

Quote

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

Quote

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

## Re: graph problem

Posted 12 November 2016 - 10:03 AM

### #8

## Re: graph problem

Posted 12 November 2016 - 10:07 AM

Proof: An exercise for the reader.

### #9

## Re: graph problem

Posted 12 November 2016 - 12:14 PM

### #10

## Re: graph problem

Posted 12 November 2016 - 12:22 PM

### #11

## Re: graph problem

Posted 12 November 2016 - 12:51 PM

### #12

### #13

## Re: graph problem

Posted 12 November 2016 - 01:07 PM

(k+1) * (\alpha(G) - |SA(G)|) <= k . => alpha(G) - |SA(G)| = 0 => alpha(G) = |SA(G)| which satisfies the condition.. Is that right?

### #14

## Re: graph problem

Posted 12 November 2016 - 01:10 PM

Quote

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

## Re: graph problem

Posted 12 November 2016 - 01:16 PM

This post has been edited by **andrewsw**: 12 November 2016 - 01:20 PM

Reason for edit:: Removed previous quote, just press REPLY