Papers for

network configuration teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Understanding how to fix improper graph colorings with limited changes

On the Parameterized Complexity of Coloring Discovery

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.

Wed 9 SeptComputational ComplexityDiscrete MathematicsData Structures and Algorithms

The gist

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.

Open → 2609.09837v1