Recursive largest first algorithm

Last updated January 04, 2023

The Recursive Largest First (RLF) algorithm is a heuristic for the NP-hard graph coloring problem. It was originally proposed by Frank Leighton in 1979.^[1]

The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a maximal independent set of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for bipartite, cycle, and wheel graphs.^[2] In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s chromatic number.

Description

The algorithm can be described by the following three steps. At the end of this process, ${\mathcal {S}}$ gives a partition of the vertices representing a feasible $|{\mathcal {S}}|$ -colouring of the graph $G$ .

Let ${\mathcal {S}}=\emptyset$ be an empty solution. Also, let $G=(V,E)$ be the graph we wish to color, comprising a vertex set $V$ and an edge set $E$ .
Identify a maximal independent set $S\subseteq V$ $Recursive largest first algorithm$ . To do this:
1. The first vertex added to $S$ should be the vertex in $G$ that has the largest number of neighbors.
2. Subsequent vertices added to $S$ should be chosen as those that (a) are not currently adjacent to any vertex in $S$ , and (b) have a maximal number of neighbors that are adjacent to vertices in $S$ . Ties in condition (b) can be broken by selecting the vertex with the minimum number of neighbors not in $S$ . Vertices are added to $S$ in this way until it is impossible to add further vertices.
Now set ${\mathcal {S}}={\mathcal {S}}\cup \{S\}$ and remove the vertices of $S$ from $G$ . If $G$ still contains vertices, then return to Step 2; otherwise end.

Example

Consider the graph $G=(V,E)$ shown on the right. This is a wheel graph and will therefore be optimally colored by RLF. Executing the algorithm results in the vertices being selected and colored in the following order:

Vertex $g$ (color 1)
Vertex $a$ , $c$ , and then $e$ (color 2)
Vertex $b$ , $d$ , and then $f$ (color 3)

This gives the final three-colored solution ${\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}$ .

Performance

Let $n$ be the number of vertices in the graph and let $m$ be the number of edges. Using big O notation, in his original publication Leighton states the complexity of RLF to be ${\mathcal {O}}(n^{3})$ ; however, this can be improved upon. Much of the expense of this algorithm is due to Step 2, where vertex selection is made according to the heuristic rules stated above. Indeed, each time a vertex is selected for addition to the independent set $S$ , information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in ${\mathcal {O}}(m)$ time, meaning that the overall complexity of RLF is ${\mathcal {O}}(mn)$ .^[2]

If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to ${\mathcal {O}}(n+m)$ ; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.^[2] It will also now be inexact for bipartite, cycle, and wheel graphs.

In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the ${\mathcal {O}}(n+m)$ greedy algorithm and the ${\mathcal {O}}((n+m)\lg n)$ DSatur algorithm on random graphs. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.^[2]

Related Research Articles

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

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 $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . 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.$

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number $ψ(G)$ of a graph $G$ is the maximum number of colors possible in any complete coloring of $G$ .

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory, a domatic partition of a graph $is a partition of into disjoint sets,,..., such that each V i is a dominating set for G . The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.$

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

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.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices.

DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979. Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, adding a previously unused colour when needed. Once a new vertex has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of colours in its neighbourhood and colours this vertex next. Brélaz defines this number as the degree of saturation of a given vertex. The contraction of the term "degree of saturation" forms the name of the algorithm. DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite, cycle, and wheel graphs. DSatur has also been referred to as saturation LF in the literature.

References

↑ Leighton, F. (1979). "A graph coloring algorithm for large scheduling problems". Journal of Research of the National Bureau of Standards. 84 (6): 489–503. doi:10.6028/jres.084.024. PMC 6756213 . PMID 34880531.
1 2 3 4 Lewis, R. (2021). A Guide to Graph Colouring: Algorithms and Applications. Texts in Computer Science. Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. S2CID 57188465.

External links

High-Performance Graph Colouring Algorithms Suite of graph coloring algorithms (implemented in C++) used in the book A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] Leighton, F. (1979). "A graph coloring algorithm for large scheduling problems". Journal of Research of the National Bureau of Standards. 84 (6): 489–503. doi:10.6028/jres.084.024. PMC 6756213 . PMID 34880531.

[:1-2] 1 2 3 4 Lewis, R. (2021). A Guide to Graph Colouring: Algorithms and Applications. Texts in Computer Science. Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. S2CID 57188465.

[1]

[2]