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 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