Графтарда максималды тәуелсіз жиынтар: комбинаторлық аспектілер

Independent set which is not a subset of any other independent set
the combinatorial aspects of maximal independent sets of vertices in a graph

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property. For example, in the graph , a path with three vertices a, b, and c, and two edges and , the sets {b} and {a, c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a, c}. In this same graph, the maximal cliques are the sets {a, b} and {b, c}. A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. A graph may have many MISs of widely varying sizes; the largest, or possibly several equally large, MISs of a graph is called a maximum independent set. The graphs in which all maximal independent sets have the same size are called well covered graphs. The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids. Two algorithmic problems are associated with MISs: finding a single MIS in a given graph and listing all MISs in a given graph.

Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximal clique irreducible and hereditary maximal clique irreducible graphs. A graph is said to be maximal clique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximal clique irreducible if the same property is true for every induced subgraph. Hereditary maximal clique irreducible graphs include triangle free graphs, bipartite graphs, and interval graphs. Cographs can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.

showed that any graph with n vertices has at most 3n/3 maximal cliques. Complementarily, any graph with n vertices also has at most 3n/3 maximal independent sets. A graph with exactly 3n/3 maximal independent sets is easy to construct: simply take the disjoint union of n/3 triangle graphs. Any maximal independent set in this graph is formed by choosing one vertex from each triangle. The complementary graph, with exactly 3n/3 maximal cliques, is a special type of Turán graph; because of their connection with Moon and Moser's bound, these graphs are also sometimes called Moon Moser graphs. Tighter bounds are possible if one limits the size of the maximal independent sets: the number of maximal independent sets of size k in any n vertex graph is at most

The graphs achieving this bound are again Turán graphs. Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. If all n vertex graphs in a family of graphs have O(n) edges, and if every subgraph of a graph in the family also belongs to the family, then each graph in the family can have at most O(n) maximal cliques, all of which have size O(1). For instance, these conditions are true for the planar graphs: every n vertex planar graph has at most 3n − 6 edges, and a subgraph of a planar graph is always planar, from which it follows that each planar graph has O(n) maximal cliques (of size at most four). Interval graphs and chordal graphs also have at most n maximal cliques, even though they are not always sparse graphs. 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.

An algorithm for listing all maximal independent sets or maximal cliques in a graph can be used as a subroutine for solving many NP complete graph problems. Most obviously, the solutions to the maximum independent set problem, the maximum clique problem, and the minimum independent dominating problem must all be maximal independent sets or maximal cliques, and can be found by an algorithm that lists all maximal independent sets or maximal cliques and retains the ones with the largest or smallest size. Similarly, the minimum vertex cover can be found as the complement of one of the maximal independent sets. observed that listing maximal independent sets can also be used to find 3 colorings of graphs: a graph can be 3 colored if and only if the complement of one of its maximal independent sets is bipartite. He used this approach not only for 3 coloring but as part of a more general graph coloring algorithm, and similar approaches to graph coloring have been refined by other authors since. Other more complex problems can also be modeled as finding a clique or independent set of a specific type. This motivates the algorithmic problem of listing all maximal independent sets (or equivalently, all maximal cliques) efficiently. It is straightforward to turn a proof of Moon and Moser's 3n/3 bound on the number of maximal independent sets into an algorithm that lists all such sets in time O(3n/3). For graphs that have the largest possible number of maximal independent sets, this algorithm takes constant time per output set. However, an algorithm with this time bound can be highly inefficient for graphs with more limited numbers of independent sets. For this reason, many researchers have studied algorithms that list all maximal independent sets in polynomial time per output set. The time per maximal independent set is proportional to that for matrix multiplication in dense graphs, or faster in various classes of sparse graphs.

The counting problem associated to maximal independent sets has been investigated in computational complexity theory. The problem asks, given an undirected graph, how many maximal independent sets it contains. This problem is #P hard already when the input is restricted to be a bipartite graph. The problem is however tractable on some specific classes of graphs, for instance it is tractable on cographs.

The maximal independent set problem was originally thought to be non trivial to parallelize due to the fact that the lexicographical maximal independent set proved to be P Complete; however, it has been shown that a deterministic parallel solution could be given by an reduction from either the maximum set packing or the maximal matching problem or by an reduction from the 2 satisfiability problem. Typically, the structure of the algorithm given follows other parallel graph algorithms that is they subdivide the graph into smaller local problems that are solvable in parallel by running an identical algorithm. Initial research into the maximal independent set problem started on the PRAM model and has since expanded to produce results for distributed algorithms on computer clusters. The many challenges of designing distributed parallel algorithms apply in equal to the maximum independent set problem. In particular, finding an algorithm that exhibits efficient runtime and is optimal in data communication for subdividing the graph and merging the independent set.

It was shown in 1984 by Karp et al. that a deterministic parallel solution on PRAM to the maximal independent set belonged in the Nick's Class complexity zoo of That is to say, their algorithm finds a maximal independent set in using , where is the vertex set size. In the same paper, a randomized parallel solution was also provided with a runtime of using processors. Shortly after, Luby and Alon et al. independently improved on this result, bringing the maximal independent set problem into the realm of with an runtime using processors, where is the number of edges in the graph. In order to show that their algorithm is in , they initially presented a randomized algorithm that uses processors but could be derandomized with an additional processors. Today, it remains an open question as to if the maximal independent set problem is in .

Distributed maximal independent set algorithms are strongly influenced by algorithms on the PRAM model. The original work by Luby and Alon et al. has led to several distributed algorithms.