Understanding how to fix improper graph colorings with limited changes
On the Parameterized Complexity of Coloring Discovery
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
Summary
Coloring Discovery looks at whether you can correct a coloring of a graph that isn’t proper by making only a few changes. The authors study three ways to change colors: recoloring a single node, swapping colors of any two nodes, or swapping colors only if nodes are connected. They find efficient algorithms for some cases but also prove that the problem is hard for others, even on simple graphs. This helps us understand when fixing color problems can be done quickly or is likely to be very difficult.
What this means in practice
- •For graph algorithm designers: Determine which graph structural parameters allow efficient recoloring fixes in algorithms that modify vertex colorings.
- •For network configuration teams: Assess when quick corrections to channel assignments represented as colorings are computationally feasible based on network topology parameters.
A theory result. No direct application yet.
Authors
Eric Decker, Sebastian Siebertz
Abstract
Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes. We study the parameterized complexity of three modification step models that were studied previously in the literature: recoloring one vertex (color flipping), swapping the colors of arbitrary vertices (color swapping), and swapping colors only across an edge (color sliding). For color flipping, we give exact fixed-parameter algorithms for the parameters vertex cover and distance to complete. For color swapping, we obtain fixed-parameter tractability for the parameter vertex cover plus the number of colors. Our lower bounds show W[1]-hardness for treedepth plus feedback vertex set in the color flipping model and for the number of colors plus bandwidth or distance to disjoint paths in the swapping and sliding models. All three variants remain NP-complete with four colors on graphs of diameter two.