Recursive largest first algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 13:35, 6 January 2022

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$ $S\subseteq V$ . 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]

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).^[2]

References

^ Leighton, F. (1979). "A graph coloring algorithm for large scheduling problems". Journal of Research of the National Bureau of Standards. 84: 489–503.
^ ^a ^b ^c ^d ^e Lewis, R. (2021). A Guide to Graph Colouring: Algorithms and Applications. Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5.

[:0-1] Leighton, F. (1979). "A graph coloring algorithm for large scheduling problems". Journal of Research of the National Bureau of Standards. 84: 489–503.

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

[1]

[2]

@@ Line 1: / Line 1: @@
 {{Short description|Algorithm for graph coloring}}
-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.<ref name=":0">{{Cite journal|last=Leighton|first=F.|date=1979|title=A graph coloring algorithm for large scheduling problems|journal=Journal of Research of the National Bureau of Standards|volume=84|pages=489–503}}</ref>
+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.<ref name=":0">{{Cite journal|last=Leighton|first=F.|date=1979|title=A graph coloring algorithm for large scheduling problems|journal=Journal of Research of the National Bureau of Standards|volume=84|pages=489–503}}</ref>
-The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying an [[Independent_set_(graph_theory)|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.
+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 try and form high-quality solutions (solutions using as few colors as possible), the RLF algorithm uses specialized heuristics to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for [[bipartite graph|bipartite]], [[cycle graph|cycle]], and [[wheel graph|wheel graphs]].<ref name=":1">{{Cite book|last=Lewis|first=R.|date=2021|title=A Guide to Graph Colouring: Algorithms and Applications|publisher=Springer|doi=
+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 graph|bipartite]], [[cycle graph|cycle]], and [[wheel graph|wheel graphs]].<ref name=":1">{{Cite book|last=Lewis|first=R.|date=2021|title=A Guide to Graph Colouring: Algorithms and Applications|publisher=Springer|doi=
-.1007/978-3-030-81054-2|isbn=978-3-030-81053-5}}</ref> In general, however, the algorithm is approximate, and may well return solutions using more colors than the graph’s [[chromatic number]].
+.1007/978-3-030-81054-2|isbn=978-3-030-81053-5}}</ref> 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, <math>\mathcal{S}</math> gives a partition of the vertices representing a feasible <math>|\mathcal{S}|</math>-colouring of the graph <math>G</math>.
-# Let <math>\mathcal{S}=\emptyset</math> be an empty solution, and let <math>G=(V,E)</math> be the graph we wish to color, comprising a vertex set <math>V</math> and an edge set <math>E</math>.
+# Let <math>\mathcal{S}=\emptyset</math> be an empty solution. Also, let <math>G=(V,E)</math> be the graph we wish to color, comprising a vertex set <math>V</math> and an edge set <math>E</math>.
 # Identify a [[maximal independent set]] <math>S\subseteq V</math>. To do this:
 ## The first vertex added to <math>S</math> should be the vertex in <math>G</math> that has the largest number of neighbors.
-## Subsequent vertices added to <math>S</math> should be chosen as those that are (a) not currently adjacent to any vertex in <math>S</math>, and (b) have a maximal number of neighbors that are adjacent to vertices in <math>S</math>. Ties in condition (b) can be broken by selecting the vertex with the minimum number of neighbors not in <math>S</math>. Vertices are added to <math>S</math> in this way until it is impossible to add further vertices.
+## Subsequent vertices added to <math>S</math> should be chosen as those that (a) are not currently adjacent to any vertex in <math>S</math>, and (b) have a maximal number of neighbors that are adjacent to vertices in <math>S</math>. Ties in condition (b) can be broken by selecting the vertex with the minimum number of neighbors not in <math>S</math>. Vertices are added to <math>S</math> in this way until it is impossible to add further vertices.
 # Now set <math>\mathcal{S}=\mathcal{S}\cup \{S\}</math> and remove the vertices of <math>S</math> from <math>G</math>. If <math>G</math> still contains vertices, then return to Step 2; otherwise end.
@@ Line 28: / Line 28: @@
 ==Performance==
-Let <math>n</math> be the number of vertices in the graph and <math>m</math> be the number of colors. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; 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 <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"></ref>
+Let <math>n</math> be the number of vertices in the graph and let <math>m</math> be the number of edges. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; 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 <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"></ref>
-If the heuristics of Step 2 are replaced with random selection, then the complexity is reduced to <math>\mathcal{O}(n+m)</math>; however, this will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref>
+If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to <math>\mathcal{O}(n+m)</math>; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref> It will also now be inexact for [[bipartite graph|bipartite]], [[cycle graph|cycle]], and [[wheel graph|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 <math>\mathcal{O}(n+m)</math> [[Greedy coloring|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph|random graphs]]. However, runtimes with RLF were also seen to be higher due to its higher overall complexity.<ref name=":1"></ref>
+In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"></ref>
 ==External links==