next up previous contents index CD CD Algorithms
Next: Vertex Cover Up: Graph Problems: Hard Problems Previous: Clique

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:

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 Source codes are available under pub/challenge/graph and test data under pub/djs. See Section gif.

Combinatorica [Ski90] provides (slow) Mathematica implementations of cliques, independent sets, and vertex covers.     See Section gif 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 tex2html_wrap_inline29317 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 gif), vertex coloring (see page gif), vertex cover (see page gif).      

next up previous contents index CD CD Algorithms
Next: Vertex Cover Up: Graph Problems: Hard Problems Previous: Clique

Mon Jun 2 23:33:50 EDT 1997