Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

Hi all, I am working through an exercise on independent sets. So far, I have checked these boxes to describe the image above:

  • A maximum size IS in this graph is 2
  • In a complement graph, node 1 must be connected to nodes 4, 5, and 6
  • A clique in a graph becomes an IS in the complement graph
  • If a node is in the IS then none of its adjacent nodes are in the IS

I am confused as to these two statements:

  • With optimization version of the IS problem, the goal is to maximize the size of the IS
  • If the size of the IS in graph G(n,m) is n, then m=0

In my class notes, I have G(V,E) where V = vertices and E = edges. If the number of vertices is n, I can't think of why the number of edges would equal zero, so I have left this unchecked. I have no idea what the optimization version is trying to imply.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

The "optimization version" is likely referring to the problem of determining the largest size of an independent set in a graph.

The other statement is saying that every vertex in your graph is part of the same independent set. Thus, there cannot be any edges.

share|improve this answer
    
thanks for the quick reply! So G(V,E) refers to the number of vertices and edges in the IS? My mistake was in thinking that it was referring to the whole graph. In this instance, that answer should have been checked. Can you elaborate more on the optimization version? Still unsure if I should check/uncheck that answer. –  raphnguyen Sep 4 '11 at 6:32
    
$G(n,m)$ is shorthand for "a graph $G$ with $n$ vertices and $m$ edges". It does refer to the entire graph. However, you are given another piece of information about $G$ - it has an independent set of size $n$. That means every vertex is in the independent set. Such a graph can't possibly have any edges. –  Austin Mohr Sep 4 '11 at 6:36
    
The optimization version of IS just means the problem of finding a computer program that can look at a graph and figure out what the largest independent set is. You should check that answer. –  Austin Mohr Sep 4 '11 at 6:37
    
thanks so much for your help. Getting late over here, but you have been a huge help both in this thread and my previous thread. –  raphnguyen Sep 4 '11 at 7:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.