Independent Set

tutorial and example
tutorial and example

Independent Set

In any subset S when the two vertices are not adjacent to each other, such a subset of vertices is called an independent set.

A single vertex in any graph is said to be an independent set. Independent set is sometime also known as internally stable set. In independent set, no two vertices will have a common edge between them.

Maximal Independent Set

A maximal independent set is an independent set in which no other vertex can be added without breaking its independence property.

Maximum Independent Set

The largest possible size of a given graph G is called as maximum independent set. The size of this set is called as independence number of G, and it is denoted by α(G). The problem of finding this set is called the maximum independent set problem.

Relation between other graph parameters

A set is independent if and only if, its complement is a vertex cover. The sum of the size of a minimum vertex cover β(G) and the largest independent set α(G) is equal to the number of vertices in the graph.

A bipartite graph with no isolated vertices has the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering.

Finding Independent sets

  • In a graph, if the input is an undirected graph and the output is a maximum independent set in the graph then it is called maximum independent set problem. If there are multiple maximum independent sets then the output is only one.
    This problem is sometimes also known as vertex packing.
  • In maximum-weight independent set problem when the input is an undirected graph with weights on its vertices then the output is always an independent set with maximum total weight.