DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979.[1] 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.[1] The contraction of the term "degree of saturation" forms the name of the algorithm.[2] DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite,[1] cycle, and wheel graphs.[2] DSatur has also been referred to as saturation LF in the literature.[3]

DSatur
ClassGraph coloring
Worst-case space complexityΟ(n2)

Pseudocode

edit

Let the "degree of saturation" of a vertex be the number of different colours being used by its neighbors. Given a simple, undirected graph   compromising a vertex set   and edge set  , the algorithm assigns colors to all of the vertices using color labels  . The algorithm operates as follows:[4]

  1. Let   be the uncolored vertex in   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.
  2. Assign   to the lowest color label not being used by any of its neighbors.
  3. 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

edit
 
Wheel graph with seven vertices and twelve edges

Consider the graph   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.)

  1. Vertex   (color 1)
  2. Vertex   (color 2)
  3. Vertex   (color 3)
  4. Vertex   (color 2)
  5. Vertex   (color 3)
  6. Vertex   (color 2)
  7. Vertex   (color 3)

This gives the final three-colored solution  .

Performance

edit

The worst-case complexity of DSatur is  , where   is the number of vertices in the graph. This is because the process of selecting the next vertex to colour takes   time, and this process is carried out   times. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in  , or   using Fibonacci heap, where   is the number of edges in the graph.[2] This produces much faster runs with sparse graphs.

DSatur is known to be exact for bipartite graphs,[1] as well as for cycle and wheel graphs.[2] In an empirical comparison by Lewis in 2021, DSatur produced significantly better vertex colourings than the greedy algorithm on random graphs with edge probability  , while in turn producing significantly worse colourings than the recursive largest first algorithm.[2]

References

edit
  1. ^ a b c d Brélaz, Daniel (1979-04-01). "New methods to color the vertices of a graph". Communications of the ACM. 22 (4): 251–256. doi:10.1145/359094.359101. ISSN 0001-0782. S2CID 14838769.
  2. ^ a b c d e Lewis, R.M.R. (2021). A Guide to Graph Colouring: Algorithms and Applications. Texts in Computer Science (2 ed.). Berlin: Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. S2CID 57188465.
  3. ^ Kubale, ed. (2004). Graph Colorings (Vol.352). Providence: American Mathematical Society. p. 13. ISBN 978-0-8218-3458-9.
  4. ^ Lewis, Rhyd (2019-01-19). "Constructive Algorithms for Graph Colouring". youtube.com. Event occurs at 3:49.
edit