8 Coloring graphs with backtracking search
Graph coloring is introduced as a way to model many practical and mathematical problems, from coloring a map to solving Sudoku and managing compiler registers. The chapter explains the core question: given a graph and a limited set of colors, can we assign colors so that no adjacent nodes share one? To support this kind of reasoning in code, the text emphasizes immutable data structures, which make it easier to explore alternatives and safely backtrack when a guess fails.
To represent graphs, the chapter first builds an immutable multidictionary, then wraps it in an immutable undirected graph type that preserves key invariants such as symmetry of edges and proper node membership. This design keeps the abstraction clean: callers work with nodes and edges instead of dictionary keys and values, and the graph type prevents invalid structures from being created. The chapter also adds convenience operations like building cliques, which are important for later examples such as Sudoku.
For coloring, the text begins with a simple recursive strategy that repeatedly removes a low-degree node, colors the smaller graph, and then assigns an available color to the removed node. This works well on many sparse graphs, but it fails when every node has too many neighbors, as in Sudoku. The chapter then develops a general backtracking framework with a reducer that eliminates impossible choices and a solver that guesses when necessary, showing how the same machinery can solve both graph-coloring problems and puzzles. It closes by noting that graph coloring is NP-complete, so backtracking may be exponential in the worst case, but it remains a useful practical approach when reductions greatly shrink the search space.
On the map of South America, four countries border one another. (Source: https://commons.wikimedia.org/wiki/File:Colored_map_south_America.png; licensed under the Creative Commons Attribution-Share Alike 4.0 International license: https://creativecommons.org/licenses/by-sa/4.0/)
A graph of South America in which adjacent countries are adjacent nodes
A valid four-coloring of South America
A typical Sudoku puzzle
Summary
- Graph theory is the part of combinatorics that studies nodes connected by edges. One of the most studied problems in graph theory is the node-coloring problem. If we have a certain number of colors and want to assign a color to each node so that no two adjacent nodes have the same color, can we do so, and if so, how?
- Graphs with many low-degree nodes can often be colored with a simple algorithm that is typically linear. Identify a node that can be colored last, recursively color the graph without that node, and then choose a color for the last node.
- More complex graphs can be colored with a backtracking algorithm. Reduce the number of possible colors for each node and then check whether the result is broken, a solution, or a partial attempt. If it’s a partial attempt, pick a node, make all possible guesses for that node, and solve recursively.
- The backtracking algorithm has the same structure as the Cartesian product algorithm: a composition of the
SelectManyoperator on sequences, but with an additional reduction step which tries to avoid enumerating portions of the solution space that can’t meet the desired constraints. - Graph coloring is an NP-complete problem in general. No known polynomial-time solution exists, but there’s no proof that one can’t exist. The best-known general algorithms are exponential. Fortunately, many practical problems are solvable in reasonable time with a good reducer.
FAQ
What is graph coloring in this chapter?
Graph coloring means assigning a color to each node so that no two adjacent nodes share the same color. The chapter uses node and vertex interchangeably, but prefers the term node.
Why is the South America map used as an example?
It provides a concrete real-world coloring problem: neighboring countries must not share a color. The example also shows that at least four colors are needed because Argentina, Bolivia, Brazil, and Paraguay all border one another.
Why do we need an immutable graph data structure?
The chapter uses immutable data structures because they work well with backtracking search. Immutability makes it easier to explore guesses, discard bad attempts, and keep previous versions of the problem state intact.
Why wrap a multidictionary in a graph type?
A wrapper graph type enforces graph invariants, such as keeping edges symmetric in an undirected graph. It also makes the code clearer by using graph terminology like nodes and edges instead of dictionary terminology like keys and values.
What is a clique?
A clique is a set of nodes in which every node is adjacent to every other node. The chapter uses cliques in both the South America discussion and the Sudoku graph model.
How does the simple recursive coloring algorithm work?
It repeatedly finds a node with degree less than the number of colors, removes it, colors the smaller graph recursively, and then assigns the removed node a color not used by its neighbors. If no such low-degree node exists, the algorithm fails.
Why does the simple coloring algorithm fail on some graphs?
It depends on always finding a node whose degree is less than the number of available colors. On graphs where every node has too many neighbors, such as the Sudoku graph, it cannot even start.
What is backtracking search?
Backtracking search is a guess-and-check strategy: make a guess, test whether it leads toward a solution, and if it fails, go back and try another guess. The chapter uses it to solve graph-coloring problems that the simple recursive method cannot handle.
Why is graph coloring considered NP-complete?
The chapter explains that graph coloring can be stated as a yes-or-no question and that a proposed coloring can be verified in polynomial time. However, no polynomial-time algorithm is known for solving all cases, which is why the problem is NP-complete.
How are Sudoku and scheduling problems related to graph coloring?
Both can be modeled as graph-coloring problems. In Sudoku, each cell is a node and digits are colors; in scheduling, tasks, classes, or variables become nodes, and conflicting items are connected by edges so that colors represent valid times or registers.
Fabulous Adventures in Data Structures and Algorithms ebook for free
