Independent set

Independent set

right|frame">
The (unexpectedly asymmetric) set of 9 blue vertices is a maximal independent set for this graph of 24 vertices.

In graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent. That is, it is a set "V" of vertices such that for every two vertices in V, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in "V". The size of an independent set is the number of vertices it contains.

A maximal independent set is an independent set such that adding any other node to the set forces the set to contain an edge.

A maximum independent set is a largest independent set for a given graph G and its size is denoted alpha(G). [Godsil & Royle 2004, p.3] The problem of finding such a set is called the maximum independent set problem and is an NP-complete problem. As such, it is very unlikely that an efficient algorithm for finding a maximum independent set of a graph exists.

The problem of deciding if a graph has an independent set of a particular size is the independent set problem. It is computationally equivalent to deciding if a graph has a clique of a particular size. This follows from the fact that if a graph has an independent set of size "k", then its complement (the graph on the same vertex set, but complementary edge set) has a clique of size "k". The decision version of Independent Set (and consequently, clique) is known to be NP-complete.

A "maximum" independent set should not be confused with a "maximal" independent set. A maximal independent set is an independent set which is not contained in any larger independent set. The problem of finding a maximal independent set can be solved in polynomial time by a trivial greedy algorithm.

Notes

See also

* an edge independent set is called Matching

References

* cite book
last = Godsil
first = Chris
coauthors = Gordon Royle
title = Algebraic Graph Theory
publisher = Springer
origyear = 1949
year = 2004
location=New York
ref = godsil49
isbn = 0-387-95220-9

External links

* http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Independent Set — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Independent set (graph theory) — The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices …   Wikipedia

  • Independent set problem — In mathematics, the independent set problem (IS) is a well known problem in graph theory and combinatorics. The independent set problem is known to be NP complete. It is almost identical to the clique problem. Description Given a graph G , an… …   Wikipedia

  • independent set — noun a set of vertices of a graph, such that no pair of them are adjacent to each other; in other words, a set of vertices which are all independent of each other Syn: coclique …   Wiktionary

  • Maximal independent set — This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For other aspects of independent vertex sets in graph theory, see Independent set (graph theory). For other kinds of independent sets, see… …   Wikipedia

  • Set packing — is a classical NP complete problem in computational complexity theory and combinatorics, and was one of Karp s 21 NP complete problems. Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k… …   Wikipedia

  • independent — I. adjective Date: 1611 1. not dependent: as a. (1) not subject to control by others ; self governing (2) not affiliated with a larger controlling unit < an independent bookstore > b. (1) not requiring or relying on something else …   New Collegiate Dictionary

  • Independent Party of Oregon — Chairman Linda Williams Secretary General Sal Peralta Founded January 24, 2007 ( …   Wikipedia

  • Independent Catholic Churches — are Christian denominations (or ) which claim apostolic succession for their bishops but are not a part of the Catholic Church, Oriental Orthodoxy, the Eastern Orthodox Churches, the Old Catholic Churches under the Archbishop of Utrecht or the… …   Wikipedia

  • Independent Baptist — churches (also referred to as Independent Fundamental Baptist , or IFB) are Christian churches holding to generally Baptist beliefs. Like all Baptists they are characterized by being independent from the authority of denominations and church… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”