💻 computer science

Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring

This paper analyzes the combinatorial landscapes of the Dominating Set and Vertex Coloring problems across various graph classes to determine whether their local optima structures are unimodal, plateau-unimodal, equimodal, or truly multimodal under both single-change and swap-based neighborhood operators.

Original authors: Johanna Gasse, Antonia Heinen, Felix Knöfel, Timo Kötzing, Maxim Stanko

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johanna Gasse, Antonia Heinen, Felix Knöfel, Timo Kötzing, Maxim Stanko

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant puzzle, but instead of fitting pieces together, you are trying to arrange a group of people in a room to satisfy specific rules. Sometimes, the rules are simple; other times, they are a tangled mess.

This paper is like a geological survey of the "terrain" of these puzzles. The authors are mapping out whether the path to the perfect solution is a smooth, straight hill, a flat plateau, or a jagged mountain range full of dead ends.

Here is a breakdown of their findings using everyday analogies.

The Two Puzzles They Studied

The researchers looked at two classic problems:

The "Watchtower" Problem (Dominating Set):
Imagine you need to place security guards in a city so that every building is either guarded or has a guard right next to it. You want to use the fewest guards possible.
- The Goal: Find the smallest team of guards.
- The Trap: You might find a team that seems perfect because moving one guard makes things worse, but it's actually a "local trap"—a team that is bigger than the absolute best possible team.
The "Party Seating" Problem (Vertex Coloring):
Imagine you are seating guests at a party. The rule is: no two people who are enemies (connected by an edge) can sit at the same table (have the same color). You want to use the fewest tables possible.
- The Goal: Use the minimum number of colors.
- The Trap: You might get stuck in a seating arrangement where you can't move anyone without causing a fight, even though a better arrangement exists.

The Map: How We Move

To solve these puzzles, you have two tools (neighborhood operators) to make changes:

The "Flip" (Single Step): You can only move one person at a time (add a guard, remove a guard, or change one person's table).
The "Flip/Swap" (Double Step): You can move one person or swap two people's positions at the same time. This gives you more flexibility.

The authors mapped out different types of "cities" (graph structures) to see if these tools could always find the best solution or if they would get stuck.

The Terrain Types (The Landscape)

They classified the puzzles into four types of terrain:

Unimodal (The Smooth Hill): There is only one peak. If you keep walking uphill (improving your solution), you are guaranteed to reach the very top. No dead ends.
Plateau-Unimodal (The Flat Summit): There is a flat top where many different solutions are equally good. You might wander around on the flat top, but you can't fall into a "worse" valley. You are still at the best possible level.
Equimodal (The Twin Peaks): There are multiple peaks, but they are all the same height. You might get stuck on one peak, but it's just as good as the other one. You haven't missed a "better" solution.
Multimodal (The Jagged Mountains): This is the dangerous terrain. There are small hills (local optima) that look like the top, but if you could fly over them, you'd see a much taller mountain nearby. If you are a "hill climber" (an algorithm that only takes small steps), you will get stuck on the small hill and never find the real peak.

What They Found

1. The Watchtower Problem (Dominating Set)

The "Flip" Tool is Weak: For many simple-looking cities (like a grid or a specific type of tree), using only single steps is a disaster. You will almost always get stuck on a "small hill" (a multimodal landscape). It's like trying to climb a mountain while only allowed to take baby steps; you'll get stuck in a valley and never see the summit.
The "Swap" Tool is Stronger: If you allow swapping guards, the terrain smooths out for many complex city types (like "Cographs" and "Interval Graphs"). The map becomes a "Plateau-Unimodal" landscape. You might wander on a flat top, but you won't get trapped in a bad valley.
The Exception: Even with the powerful "Swap" tool, some specific, weirdly shaped cities (like a bouquet of connected rings) still have jagged mountains with dead ends.

2. The Party Seating Problem (Vertex Coloring)

Simple Cities are Easy: For some very structured cities (like "Universal Bipartite Graphs" where one person knows everyone else), the terrain is a smooth hill. You can't get lost.
The "Ring" Trap: If the city is just a big ring of people (like a 6-person cycle), and you only use single steps, you can get stuck in a "local trap" where you are using 3 tables, but you could have used 2.
The "Swap" Saves the Day: For rings and "Crown Graphs" (a specific party layout), allowing swaps makes the terrain smooth again. You can always find the best seating plan.
The "Spoked" Trap: However, the authors invented a new, slightly more complex city called a "Spoked C12k" (a ring with extra connections). Even with the powerful "Swap" tool, this city is a jagged mountain range. You can get stuck in a 3-table arrangement that looks perfect locally, but a 2-table arrangement exists that you simply cannot reach without breaking the rules temporarily.

The Big Takeaway

The paper doesn't tell you how to solve these puzzles faster. Instead, it tells you which puzzles are "tricky" by nature.

If a puzzle is Multimodal, it means a simple "try and improve" strategy will likely fail. You need a more complex strategy that can jump over hills or swap pieces around.
If a puzzle is Unimodal or Plateau-Unimodal, it means a simple strategy will eventually work, even if it takes a long time to walk the path.

The authors essentially drew a map for computer scientists, showing exactly where the "dead ends" are hidden in these two famous problems, so they know when to use simple tools and when they need to bring out the heavy machinery.

Technical Summary: Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring

Problem Definition

This paper investigates the combinatorial landscapes of two fundamental graph problems: Dominating Set and Vertex Coloring. The optimization goal for Dominating Set is to find a cardinality-minimal set $S \subseteq V$ such that every vertex is either in $S$ or adjacent to a vertex in $S$ . For Vertex Coloring, the goal is to assign colors to vertices such that no two adjacent vertices share a color, minimizing the total number of colors used.

The authors analyze these problems not by deriving runtime bounds for specific algorithms, but by characterizing the existence and nature of local optima within the search space. The study focuses on whether the induced landscapes are:

Unimodal: Exactly one local optimum plateau of size 1.
Plateau-unimodal: Exactly one local optimum plateau (which may contain multiple solutions of equal fitness).
Equimodal: All local optimum plateaus have equal fitness (i.e., all are global optima).
Multimodal: The existence of Non-Global Local Optima (NGLOs) or Non-Global Local Optimum Plateaus (NGLOPs), where a local optimum has strictly worse fitness than the global optimum.

The analysis is conducted under two distinct neighborhood operators:

Flip ( $N_{flip}$ ): Allows adding or removing a single element (vertex) from the solution set or changing the color of a single vertex.
Flip/Swap ( $N_{f/s}$ ): Allows a Flip operation or a Swap operation (interchanging two elements or swapping the colors of two vertices).

Methodology

The authors model fitness landscapes as triples $(X, N, f)$ , where $X$ is the set of individuals (bit strings for Dominating Set, color strings for Vertex Coloring), $N$ is the neighborhood graph, and $f$ is the fitness function.

Fitness Functions:
- For Dominating Set, the fitness function minimizes the set cardinality while imposing a heavy penalty ( $n+1$ ) for every undominated vertex. This ensures that infeasible solutions (non-dominating sets) are strictly worse than any feasible dominating set.
- For Vertex Coloring, the fitness function minimizes the number of colors used, with a heavy penalty for monochromatic edges. The analysis focuses on feasible solutions, as infeasible solutions can always be improved by recoloring a conflicting vertex.
Analytical Approach:
- The paper derives mathematical proofs rather than experimental results.
- For Dominating Set, the authors utilize reconfiguration theory, specifically the concept of canonical dominating sets and reconfiguration sequences (TAR: Token Addition and Removal). They leverage existing results on the connectivity of reconfiguration graphs for specific graph classes (trees, cographs, interval graphs) to prove the existence of positive paths between local optima and global optima under the Flip/Swap neighborhood.
- For Vertex Coloring, the authors employ structural graph theory and properties of reconfiguration graphs for proper colorings (referencing Bonamy et al.) to establish connectivity and equimodality.
- For negative results (multimodality), the authors construct specific graph instances (e.g., unbalanced bipartite graphs, specific trees, spoked cycles) and prove the existence of local optima that cannot reach a global optimum via the defined neighborhood operators.

Key Contributions and Results

1. Dominating Set

The paper classifies the landscape modality for various graph classes under both $N_{flip}$ and $N_{f/s}$ .

Flip Neighborhood ( $N_{flip}$ ):
- Multimodality: Even simple graph classes like unbalanced bipartite graphs and complete bipartite graphs (with partitions $>2$ ) induce multimodal landscapes. In these cases, the two partitions of the bipartite graph often form local optima, but one is strictly larger than the other.
- Trees: The landscape is equimodal if and only if the tree is a Corona tree (a tree where every vertex is either a leaf or adjacent to exactly one leaf). For all other trees, the landscape is multimodal.
- Simplicial-Cluster Graphs: These induce an equimodal landscape but are not plateau-unimodal (multiple distinct local optima exist).
Flip/Swap Neighborhood ( $N_{f/s}$ ):
- Plateau-Unimodality: Using reconfiguration theory, the authors prove that cographs, trees, and interval graphs admit a canonical dominating set. Consequently, any dominating set can be transformed into a global optimum via a sequence of swaps and flips without increasing the set size beyond a specific bound. Thus, these classes induce plateau-unimodal landscapes.
- Non-Unimodality: Despite being plateau-unimodal, these classes are not strictly unimodal; they contain multiple distinct local optima (e.g., $P_{3k+2}$ ).
- Multimodality: The authors identify a class of graphs called $n$ -bouquets of 6-cycles (cycles joined at a single vertex) that induce multimodal landscapes even under the Flip/Swap neighborhood.

2. Vertex Coloring

Flip Neighborhood ( $N_{flip}$ ):
- Unimodality: Universal bipartite graphs (bipartite graphs with at least one vertex connected to all vertices in the opposite partition) induce unimodal landscapes.
- Equimodality: Chordal graphs and chordal bipartite graphs induce equimodal landscapes. For chordal bipartite graphs, this implies unimodality due to the uniqueness of 2-colorings up to permutation.
- Multimodality: The landscape is multimodal for $C_{6k}$ cycles and $k$ -crown graphs ( $k > 2$ ) when specific structural conditions are met (e.g., the presence of 3-chordless $C_{6k}$ subgraphs). These graphs admit local optima at 3 (or $k$ ) colors that cannot be reduced to 2 colors via single flips.
Flip/Swap Neighborhood ( $N_{f/s}$ ):
- Unimodality: $C_{6k}$ cycles and $k$ -crown graphs become unimodal under the Flip/Swap neighborhood. The ability to swap colors allows the algorithm to escape local optima that trap the Flip operator.
- Multimodality: The authors introduce spoked $C_{12k}$ graphs (cycles with specific chords added). These graphs induce multimodal landscapes even under Flip/Swap, demonstrating that even simple graph structures with added chords can create fundamental barriers for local search.

Significance and Claims

The paper claims to extend theoretical understanding of randomized search heuristics by shifting focus from runtime bounds to problem characteristics regarding local optima.

Identifying Hardness Sources: The results explicitly delineate which problem classes suffer from local optima (requiring non-local operators like swaps) and which admit hill climbing in principle.
Operator Selection: The analysis highlights that for many graph classes (e.g., trees for Dominating Set, cycles for Vertex Coloring), the choice of neighborhood operator is critical. While $N_{flip}$ often leads to multimodal landscapes with NGLOs, $N_{f/s}$ can resolve these issues for specific classes (like trees and cographs) but fails for others (like $n$ -bouquets or spoked cycles).
Foundation for Future Analysis: The authors state that identifying the absence of NGLOs (equimodality or plateau-unimodality) allows future research to proceed with finer runtime analyses, knowing that "fundamental road blocks" (local optima) are absent, and difficulties may instead stem from long paths or large plateaus.

The work does not propose new algorithms or experimental applications but provides a rigorous mathematical classification of the landscape topology for these combinatorial problems, serving as a theoretical baseline for understanding the behavior of local search heuristics.