Independent Set (graph Theory) - Finding Independent Sets

Finding Independent Sets

Further information: Clique problem

In computer science, several computational problems related to independent sets have been studied.

  • In the maximum independent set problem, the input is an undirected graph, and the output is a maximum independent set in the graph. If there are multiple maximum independent sets, only one need be output.
  • In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. The maximum independent set problem is the special case in which all weights are one.
  • In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets.
  • In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.

The first three of these problems are all important in practical applications; the independent set decision problem is not, but is necessary in order to apply the theory of NP-completeness to problems related to independent sets.

The independent set problem and the clique problem are complementary: a clique in G is an independent set in the complement graph of G and vice versa. Therefore, many computational results may be applied equally well to either problem. For example, the results related to the clique problem have the following corollaries:

  • The decision problem is NP-complete, and hence it is not believed that there is an efficient algorithm for solving it.
  • The maximum independent set problem is NP-hard and it is also hard to approximate.

Read more about this topic:  Independent Set (graph Theory)

Famous quotes containing the words finding, independent and/or sets:

    “When any one of our relations was found to be a person of a very bad character, a troublesome guest, or one we desired to get rid of, upon his leaving my house I ever took care to lend him a riding-coat, or a pair of boots, or sometimes a horse of small value, and I always had the satisfaction of finding he never came back to return them.”
    —Oliver Goldsmith (1728–1774)

    “For myself I found that the occupation of a day-laborer was the most independent of any, especially as it required only thirty or forty days in a year to support one. The laborer’s day ends with the going down of the sun, and he is then free to devote himself to his chosen pursuit, independent of his labor; but his employer, who speculates from month to month, has no respite from one end of the year to the other.”
    —Henry David Thoreau (1817–1862)

    “Drink, sir, is a great provoker of three things ... nose-painting, sleep, and urine. Lechery, sir, it provokes and unprovokes: it provokes the desire but it takes away the performance. Therefore much drink may be said to be an equivocator with lechery: it makes him and it mars him; it sets him on and it takes him off.”
    —William Shakespeare (1564–1616)