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:

    “At the age of twelve I was finding the world too small: it appeared to me like a dull, trim back garden, in which only trivial games could be played.”
    —Elizabeth Bowen (1899–1973)

    “[My father] was a lazy man. It was the days of independent incomes, and if you had an independent income you didn’t work. You weren’t expected to. I strongly suspect that my father would not have been particularly good at working anyway. He left our house in Torquay every morning and went to his club. He returned, in a cab, for lunch, and in the afternoon went back to the club, played whist all afternoon, and returned to the house in time to dress for dinner.”
    —Agatha Christie (1891–1976)

    “To the extent to which genius can be conjoined with a merely good human being, Haydn possessed genius. He never exceeds the limits that morality sets for the intellect; he only composes music which has “no past.””
    —Friedrich Nietzsche (1844–1900)