Independent Set

  

 

Input description: A graph G=(V,E).

Problem description: What is the largest subset S of vertices of V such that no pair of vertices in S defines an edge of E between them?

Discussion: The need to find large independent sets typically arises in dispersion problems, where we seek a set of mutually separated points.     For example, suppose you are trying to identify locations for a new franchise service such that no two locations are close enough to compete with each other.   Construct a graph where the vertices are possible locations, and add edges between any two locations deemed close enough to interfere. The maximum independent set gives you the maximum number of franchises you can sell without cannibalizing sales.

Independent sets avoid conflicts between elements and hence arise often in coding theory and scheduling problems.   Define a graph whose vertices represent the set of possible code words, and add edges between any two code words sufficiently similar to be confused due to noise. The maximum independent set of this graph defines the highest capacity code for the given communication channel.   

Independent set is closely related to two other NP-complete problems:

• Vertex coloring - A coloring of a graph G is in fact a partitioning of the vertices of G into a small number of independent sets, since any two vertices of the same color cannot have an edge between them. In fact, most scheduling applications of independent set are really coloring problems, since all tasks eventually must be completed.
• Clique - The complement of a graph G = (V,E) is a graph G' = (V,E'), where iff (i,j) is not in E.   In other words, we replace each edge by a nonedge and vica versa. The maximum independent set in G is exactly the maximum clique in G', so these problems are essentially identical. Algorithms and implementations in Section can thus be easily used for independent set.

The simplest reasonable heuristic is to find the lowest-degree vertex, add it to the independent set, and delete it and all vertices adjacent to it.   Repeating this process until the graph is empty gives a maximal independent set, in that it can't be made larger just by adding vertices. Using randomization or perhaps some exhaustive search to distinguish among the low-degree vertices might result in somewhat larger independent sets.

The independent set problem is in some sense dual to the graph matching problem.   The former asks for a large set of vertices with no edge in common, while the latter asks for a large set of edges with no vertex in common. This suggests trying to rephrase your problem as a matching problem, which can be computed in polynomial time, while the maximum independent set problem is NP-complete.

The maximum independent set of a tree can be found in linear time by   (1) stripping off the leaf nodes, (2) adding them to the independent set, (3) deleting the newly formed leaves, and then (4) repeating from the first step on the resulting tree until it is empty.

Implementations: Programs for the closely related problems of finding cliques and independent sets were sought for the Second DIMACS Implementation Challenge, held in October 1993.   Programs and data from the challenge are available by anonymous ftp from dimacs.rutgers.edu. Source codes are available under pub/challenge/graph and test data under pub/djs. See Section .

Combinatorica [Ski90] provides (slow) Mathematica implementations of cliques, independent sets, and vertex covers.     See Section for further information on Combinatorica.

Neural-network heuristics for vertex cover and related problems such as clique and vertex coloring have been implemented in C   and Mathematica by Laura Sanchis and Arun Jagota, and are available in the algorithm repository http://www.cs.sunysb.edu/ algorith.

Notes: Independent set remains NP-complete for planar cubic graphs [GJ79]. However, it can be solved efficiently for bipartite graphs [Law76].

Related Problems: Clique (see page ), vertex coloring (see page ), vertex cover (see page ).