computer science

Independent set (graph theory)

Independent set (graph theory) is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Independent set (graph theory) rather than just read about it. In short: In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S {\displaystyle S} of vertices such that for every two vertices in S {\displaystyle S} , there is no edge connecting the two.

Key takeaways

Independent set (graph theory) belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Independent set (graph theory) to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Independent set (graph theory) from memory before moving on to harder problems.

Reference excerpt

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S {\displaystyle S} of vertices such that for every two vertices in S {\displaystyle S} , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S {\displaystyle S} . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G {\displaystyle G} . This size is called the independence number of G {\displaystyle G} and is usually denoted by α ( G ) {\displaystyle \alpha (G)} . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph. Every maximum independent set also is maximal, but the converse implication does not necessarily hold.

Properties

Relationship to other graph parameters A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory. A set is independent if and only if its complement is a vertex cover. Therefore, the sum of the size of the largest independent set α ( G ) {\displaystyle \alpha (G)} and the size of a minimum vertex cover β ( G ) {\displaystyle \beta (G)} is equal to the number of vertices in the graph. A vertex coloring of a graph G {\displaystyle G} corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number χ ( G ) {\displaystyle \chi (G)} , is at least the quotient of the number of vertices in G {\displaystyle G} and the independent number α ( G ) {\displaystyle \alpha (G)} . In a bipartite graph with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is Kőnig's theorem.

Maximal independent set

An independent set that is not a proper subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3n/3 maximal independent sets, but many graphs have far fewer. The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence. Therefore, both numbers are proportional to powers of 1.324718..., the plastic ratio.

Finding independent sets

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. This problem is sometimes referred to as "vertex packing". 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.

Maximum independent sets and maximum cliques 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 independent set 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. Despite the close relationship between maximum cliques and maximum independent sets in arbitrary graphs, the independent set and clique problems may be very different when restricted to special classes of graphs. For instance, for sparse graphs (graphs in which the number of edges is at most a constant times the number of vertices in any subgraph), the maximum clique has bounded size and may be found exactly in linear time; however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is MAXSNP-complete, implying that, for some constant c (depending on the degree) it is NP-hard to find an approximate solution that comes within a factor of c of the optimum.

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Independent set (graph theory)

Start with the simplest possible case. Write down what Independent set (graph theory) claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Independent set (graph theory) before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Independent set (graph theory) ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Independent set (graph theory)

In research: Independent set (graph theory) appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Independent set (graph theory) in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Independent set (graph theory) is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational problems in graph theory, Graph theory objects, NP-complete problems, so understanding it makes those chapters shorter.
In everyday life: Look for Independent set (graph theory) outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Independent set (graph theory) in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Independent set (graph theory) means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Independent set (graph theory) out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Independent set (graph theory) in simple terms?

Why does Independent set (graph theory) matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Independent set (graph theory)?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Independent set (graph theory).