Stable amount

In graph theory, a stable set , independent set or co-clique is a subset of nodes of a graph that are not adjacent to one another . Deciding whether a graph contains a stable set of a certain minimum size is called a stability problem and, like finding a largest stable set, is algorithmically difficult.

Definitions

The nine blue nodes form a maximum stable set.

Stable amount

Let be an undirected graph without multiple edges and a subset of . Applies for any two different nodes , and in that they are not adjacent are, it is called a stable and independent set of the graph. ${\ displaystyle G = (V, E)}$ ${\ displaystyle U}$ ${\ displaystyle V}$ ${\ displaystyle v}$ ${\ displaystyle w}$ ${\ displaystyle U}$ ${\ displaystyle U}$

Maximum stable amount

A stable set of is called maximal if one cannot add another node from to , so that together with is a stable set. If there is no stable set that contains more elements than it is called the largest stable set . The number of elements of a largest stable set is called the stability or independence number . Instead of using subsets of , one also defines stable sets as special subgraphs . ${\ displaystyle U}$ ${\ displaystyle G}$ ${\ displaystyle v}$ ${\ displaystyle V \ setminus U}$ ${\ displaystyle U}$ ${\ displaystyle U}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle U}$ ${\ displaystyle U}$ ${\ displaystyle V}$

Outwardly stable amount

A subset of nodes in a directed graph is called externally stable or dominant if every node in has a positive neighbor in . The thickness of a smallest dominant set is called the domination number of the graph . A set of nodes in a directed graph is called the core of the graph if it is both stable and dominant. ${\ displaystyle D}$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle V \ setminus D}$ ${\ displaystyle D}$ ${\ displaystyle \ gamma (G)}$ ${\ displaystyle G}$

property

Every stable set of a graph is a clique in the complement graph.

Problems and complexities

The decision problem for a graph G and a natural number k to decide whether G contains a stable set of size at least k is called the stability problem. The associated optimization problem asks for the stability number of a graph. The associated search problem asks for a largest stable set. These three problems are polynomially equivalent.

The stability problem is NP- complete , the associated optimization and search problem is NP-equivalent . The NP severity of the stability problem can easily be shown by reducing the clique problem to the stability problem by forming the complement graph .

In bipartite graphs, the largest stable set can be calculated in polynomial time. In fact, it is even more true that the stability number in perfect graphs can be calculated in polynomial time. The calculation of a maximum stable set is already possible with a simple greedy algorithm .