DSatur

{{short description|Graph colouring algorithm by Daniel Brélaz}} {{Infobox algorithm |name = DSatur  |class = Graph coloring  |image =  |caption = |data = |time =  |best-time = |average-time = |space = ''Ο''(''n''<sup>2</sup>)  }} '''DSatur''' is a graph colouring algorithm put forward by Daniel Brélaz in 1979.<ref name=":0">{{Cite journal|last=Brélaz|first=Daniel|date=1979-04-01|title=New methods to color the vertices of a graph|journal=Communications of the ACM|volume=22|issue=4|pages=251–256|doi=10.1145/359094.359101|s2cid=14838769 |issn=0001-0782|doi-access=free}}</ref> 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.<ref name=":0" /> The contraction of the term "degree of saturation" forms the name of the algorithm.<ref name=":1">{{Cite book|title=A Guide to Graph Colouring: Algorithms and Applications|last=Lewis|first=R.M.R.|series=Texts in Computer Science |publisher=Springer|year=2021|isbn=978-3-030-81053-5|edition=2|location=Berlin|pages=|doi=10.1007/978-3-030-81054-2|s2cid=57188465 }}</ref> DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite,<ref name=":0" /> cycle, and wheel graphs.<ref name=":1" /> DSatur has also been referred to as saturation LF in the literature.<ref>{{Cite book|title=Graph Colorings (Vol.352)|last=|first=|publisher=American Mathematical Society|year=2004|isbn=978-0-8218-3458-9|editor-last=Kubale|location=Providence|pages=13}}</ref>

== Pseudocode == Let the "degree of saturation" of a vertex be the number of different colours being used by its neighbors. Given a simple, undirected graph <math>G</math> compromising a vertex set <math>V</math> and edge set <math>E</math>, the algorithm assigns colors to all of the vertices using color labels <math>1,2,3,...</math>. The algorithm operates as follows:<ref>{{Cite web|url=https://www.youtube.com/watch?v=L2csXWQMsNg|title=Constructive Algorithms for Graph Colouring|last=Lewis|first=Rhyd|date=2019-01-19|website=youtube.com|archive-url=|archive-date=|url-status=|access-date=|time=3:49}}</ref>

# Let <math>v</math> be the uncolored vertex in <math>G</math> with the highest degree of saturation. In cases of ties, choose the vertex among these with the largest degree in the subgraph induced by the uncolored vertices. # Assign <math>v</math> to the lowest color label not being used by any of its neighbors. # If all vertices have been colored, then end; otherwise return to Step 1.

Step 2 of this algorithm assigns colors to vertices using the same scheme as the greedy colouring algorithm. The main differences between the two approaches arises in Step 1 above, where vertices seen to be the most "constrained" are coloured first.

==Example== thumb|Wheel graph with seven vertices and twelve edges Consider the graph <math>G=(V,E)</math> shown on the right. This is a wheel graph and will therefore be optimally colored by the DSatur algorithm. Executing the algorithm results in the vertices being selected and colored as follows. (In this example, where ties occur in both of DSatur's heuristics, the vertex with lowest lexicographic labelling among these is chosen.)

# Vertex <math>g</math> (color 1) # Vertex <math>a</math> (color 2) # Vertex <math>b</math> (color 3) # Vertex <math>c</math> (color 2) # Vertex <math>d</math> (color 3) # Vertex <math>e</math> (color 2) # Vertex <math>f</math> (color 3)

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

== Performance == The worst-case complexity of DSatur is <math>O(n^2)</math>, where <math>n</math> is the number of vertices in the graph. This is because the process of selecting the next vertex to colour takes <math>O(n)</math> time, and this process is carried out <math>n</math> times. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in <math>O((n+m)\log n)</math>, or <math>O(m+n\log n)</math> using Fibonacci heap, where <math>m</math> is the number of edges in the graph.<ref name=":1" /> This produces much faster runs with sparse graphs.

DSatur is known to be exact for bipartite graphs,<ref name=":0" /> as well as for cycle and wheel graphs.<ref name=":1" /> In an empirical comparison by Lewis in 2021, DSatur produced significantly better vertex colourings than the greedy algorithm on random graphs with edge probability <math>p=0.5</math>, while in turn producing significantly worse colourings than the recursive largest first algorithm.<ref name=":1" />

== References ==  {{reflist}}

== External links == * [https://gcol.readthedocs.io/en/latest/ ''GCol''] An open-source python library for graph coloring featuring DSatur. * [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph colouring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021). * [https://www.geeksforgeeks.org/dsatur-algorithm-for-graph-coloring/ ''C++ implementation of the DSatur Algorithm''], presented as part of the article [https://www.geeksforgeeks.org/dsatur-algorithm-for-graph-coloring/ The DSatur Algorithm for Graph Coloring], [https://www.geeksforgeeks.org/ Geeks for Geeks] (2021)

Category:1979 in computing Category:Graph algorithms Category:Graph coloring