1
$\begingroup$

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.

1 Answers 1

2

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.

  • 0
    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.2011-09-04
  • 0
    $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.2011-09-04
  • 0
    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.2011-09-04
  • 0
    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.2011-09-04