Source-linked AI summary
On the Parameterized Complexity of Coloring Discovery
Eric Decker, Sebastian Siebertz
TL;DR
Coloring Discovery asks whether a possibly improper coloring can be repaired within a move budget. The paper analyzes flipping, swapping, and sliding and proves new fixed-parameter results and structural-parameter hardness bounds, including four-color NP-completeness on diameter-two graphs.
Problem
Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed budget of allowed changes.
Source: §1 · pp. 1–2Method
The paper analyzes flipping, swapping, and sliding, proving parameterized algorithms and lower bounds for structural graph parameters.
Source: §1 · p. 4Results
Flipping is fixed-parameter tractable for vertex cover and distance to complete, swapping for vertex cover plus colors, and all three variants are NP-complete with four colors on diameter-two graphs.
Source: §1 · p. 4, §4.3 · p. 11Takeaways & Limitations
The results expand the parameterized-complexity landscape of Coloring Discovery across the three movement rules and natural structural graph parameters.
Source: §5 · p. 12Whether sliding is fixed-parameter tractable for vertex cover plus colors remains open; the swap algorithm’s need for the number of colors in its parameter also remains unresolved.
Source: §5 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies bounded-step repair of possibly infeasible colorings and establishes new algorithmic and hardness results for three movement rules. Its results add to the parameterized-complexity landscape of Coloring Discovery.
Introduction
- Repair matters when an existing assignment should be retained: a new timetable conflict or transmitter interference may be fixed with limited changes rather than rebuilding the assignment.The paper notes that retuning many devices is costly and that the initial assignment cannot simply be discarded.Source: §1 · pp. 1–2
- Coloring Discovery asks whether a possibly infeasible current state can reach any feasible state within a move budget, without requiring intermediate states to be feasible.Unlike reconfiguration, the target is not prescribed; the framework takes a base instance, initial configuration, and budget.Source: §1 · p. 2
- The paper studies flipping, which recolors one vertex; swapping, which exchanges arbitrary vertices’ colors; and sliding, which exchanges colors across an edge.The initial coloring may be improper, and the target coloring is not prescribed.Source: §1 · p. 2
Our results
- Flipping admits exact fixed-parameter algorithms for vertex cover and distance to complete, while swapping is fixed-parameter tractable for vertex cover plus the number of colors; the corresponding sliding parameterization remains open.The stated running times are 2^O(k log k)(n + m) for vertex cover and 2^O(k^2)n^3 for distance to complete.Source: §1 · p. 4
- Flip is W[1]-hard for treedepth plus feedback vertex set; swap and slide are W[1]-hard for colors plus bandwidth or distance to disjoint paths, and all three are NP-complete with four colors at diameter two.The paper also derives para-NP-completeness for colors combined with diameter, radius, or domination number.Source: §1 · p. 4
2 Preliminaries
The preliminaries define Coloring Discovery’s inputs and move rules, graph parameters, and tools used to state reachability and hardness results.
Problem definitions
- An instance is a graph, a possibly improper q-coloring, and a move budget; flips recolor one vertex, swaps exchange arbitrary vertices’ colors, and slides swap colors across an edge.Only the target coloring must be proper.Source: §2 · p. 4
Graph parameters
- Vertex cover, distance to complete, and feedback vertex set measure deletions leaving no edges uncovered, a clique, or a forest, respectively.Treedepth is defined through rooted-forest closures; bandwidth measures the largest edge span in a vertex ordering, and distance to disjoint paths counts deletions leaving disjoint paths.Source: §2 · p. 4
- For connected graphs, diameter is the greatest pairwise distance, radius the minimum maximum distance from a vertex, and domination number the smallest closed-neighborhood cover of the vertices.Source: §2 · p. 5
Parameterized complexity
- Under standard parameterized-complexity notions, a parameterized reduction maps (I,k) in time f(k)|I|^O(1) to an equivalent instance (I′,k′), with k′ ≤ g(k) for computable functions f and g.An ILP with p integer variables and binary encoding length L can be solved in f(p)L^O(1) time.Source: §2 · p. 5
Equitable coloring
- An equitable q-coloring is proper with class sizes differing by at most one; its known hardness for colors plus distance to disjoint paths also yields hardness for colors plus bandwidth.The bandwidth consequence uses an interval-graph ordering by nondecreasing left endpoint.Source: §2 · p. 5
3 Algorithms
Color flipping has exact fixed-parameter algorithms for vertex cover and distance to complete, while color swapping is fixed-parameter tractable for vertex cover plus the number of colors. The swapping algorithm uses a cycle-based ILP; its transition-multigraph approach does not seem to extend to color sliding.
3.1 Color flipping
- 2^O(k log k)(n + m) time suffices to compute the minimum flips or determine that no proper q-coloring exists when k = vc(G).Source: §3.1 · p. 5
- For vertex cover C, the flip algorithm partitions C into independent blocks and assigns distinct colors to minimize the flips needed for a proper extension.An extension to the independent set exists exactly when each vertex has fewer than q neighboring blocks.Source: §3.1 · p. 6
- For k = dtc(G), the algorithm computes the minimum flips needed to reach a proper coloring in 2^O(k^2)n^3 time.The clique remaining after removing the modulator requires pairwise-distinct colors.Source: §3.1 · p. 6
3.2 Color swapping
- Swap-CD is fixed-parameter tractable parameterized by vc(G) + q.The algorithm uses an ILP over neighborhood classes and directed color-transition cycle types to encode proper targets and swap budgets.Source: §3.2 · pp. 8–9
- The swap ILP uses color-transition multiplicities and cycle variables; its cycle equations enforce equal color histograms and its budget constrains swap distance.Source: §3.2 · pp. 8–9
- The transition-multigraph approach does not seem to extend to slides because available moves depend on color positions, leaving Slide-CD parameterized by vc(G) + q unresolved.Source: §3.2 · p. 9
4 Hardness Results
The paper establishes hardness for several structural parameterizations of Coloring Discovery, including a fixed four-color, diameter-two boundary. The results distinguish the three move models and leave open whether some tractable parameterizations extend further.
4.1 Flipping: treedepth and feedback vertex set
- Flip-CD is W[1]-hard parameterized by td(G) + fvs(G).The reduction from List Coloring bounds both parameters using the source instance’s vertex cover.Source: §4.1 · pp. 9–10
4.2 Swapping and sliding: bandwidth and distance to paths
- Swap-CD and Slide-CD are W[1]-hard parameterized by q + bw(G) and by q + ddp(G).For q + ddp(G), hardness holds even with a dominating vertex; the slide reduction uses a clique chain to connect components while preserving a parameter bound.Source: §4.2 · p. 10
4.3 The four-color lower bound
- All three variants are NP-complete on connected graphs of diameter exactly two, even with exactly four available colors.The result also implies para-NP-completeness on connected graphs parameterized by q with diameter, radius, or domination number.Source: §4.3 · p. 11
4.4 A uniform-base lower bound
- Unless ETH fails, no universal constant θ gives an O(θ^vc(G)n^O(1)) algorithm for any variant simultaneously for every fixed q.The proof transfers the q-Coloring lower bound to flipping, swapping, and sliding.Source: §4.4 · p. 12
5 Conclusion
The conclusion contrasts the mechanisms behind the three move models and notes that even diameter two does not make repair easy. It leaves several extensions of the algorithms unresolved.
5 Conclusion
- Flips permit independent calculation outside a small modulator, while swaps preserve color-class sizes and use cycle decompositions; slides also depend on color positions.A cycle decomposition of the color-transition multigraph supports exact swap-distance calculation through an ILP.Source: §5 · p. 12
- A common diameter-two reduction shows that radius one and a dominating vertex do not by themselves make Coloring Discovery easy.The conclusion applies this observation across the three modification models.Source: §5 · p. 12
- Whether Slide-CD is FPT for vc(G)+q, whether q can be removed from the swap parameter, and whether the flip algorithm extends to distance to cluster remain open.Distance to cluster means deleting a set of vertices to leave a disjoint union of cliques.Source: §5 · p. 12
A.1 The vertex-cover assignment algorithm
The vertex-cover algorithm searches over target color-class partitions of the cover and solves a weighted assignment to minimize the required flips. It computes the exact optimum or reports that no proper coloring exists.
A.1 The vertex-cover assignment algorithm
- The algorithm enumerates independent-block partitions of the vertex cover and assigns distinct colors to blocks while minimizing the flips needed for a proper extension.Vertices outside the cover form an independent set, so changed vertices there can be recolored without conflicts among themselves.Source: §A.1 · p. 16
- For each partition, choosing the color injection is a rectangular assignment problem with edge costs equal to the flip costs for a block-color pair.A square minimum-weight perfect matching can be obtained by adding zero-cost dummy block vertices.Source: §A.1 · p. 16
- The algorithm runs in 2^O(k log k)(n + m) time and computes the minimum flips or determines that no proper q-coloring exists.Here k is the vertex-cover number.Source: §A.1 · p. 17
A.2 The distance-to-complete algorithm
For distance to complete, the algorithm represents target colorings using partitions of the modulator and guesses how their colors may be reused on the remaining clique. A weighted matching then minimizes the flips for each feasible guess.
A.2 The distance-to-complete algorithm
- The algorithm partitions the modulator into independent color blocks and guesses whether each block’s color is absent from the clique or reused by one vertex of an anticomplete clique type.The clique is partitioned into at most 2^k neighborhood types, and each feasible guess must respect available vertices and the palette size.Source: §A.2 · p. 17
- For each feasible partition and guess, assignment nodes are matched injectively to color names, with costs counting the minimum flips for blocks and clique vertices.For each type, at most one vertex can retain any target color already present in that type.Source: §A.2 · pp. 17–18
- The algorithm enumerates at most (k + 1)^k partitions and at most (2k + 1)^k guesses per partition, solving each assignment in O(n^3) time.The passage gives the resulting running-time expression as (2^k + 2^O(k^2+k log k+k))n^3.Source: §A.2 · p. 19
B The Color-Cycle ILP in Detail
The color-cycle ILP encodes proper target colorings and whether their color transitions can be realized within the swap budget. Its feasible solutions correspond to reachable proper colorings, and Lenstra’s algorithm yields fixed-parameter tractability.
The Color-Cycle ILP in Detail
- The ILP assigns counts x_R,a,c to vertices in each neighborhood class and initial-color subclass, forbidding assignments that conflict with guessed cover colors.Supply equations account for every vertex in each subclass; forbidden-color equations enforce properness across edges from the cover to the independent set.Source: B The Color-Cycle ILP in Detail · p. 19
- Cycle variables y_Z encode transition multiplicities, and their arc equations ensure that every color’s outgoing and incoming transition counts balance.The resulting balanced transition multigraph decomposes into directed cycles, including one-vertex loops.Source: B The Color-Cycle ILP in Detail · p. 19
- A feasible integer solution yields a proper target coloring reachable within budget, while any reachable proper target supplies variables satisfying the ILP.The forward direction uses the budget inequality and Lemma 2; the reverse direction uses a minimum-distance cycle decomposition and Lemma 2.Source: B The Color-Cycle ILP in Detail · p. 19
- Lenstra’s algorithm across the qk choices for γ gives running time f(k + q) · n^O(1), with polynomially bounded encoding length.The formulation has at most 2kq^2 variables of type x and q + P variables of type y; b can be replaced by min{b, n−1}.Source: B The Color-Cycle ILP in Detail · p. 19
C.1 List enforcement for flipping
A list-coloring instance is transformed into a flipping instance using pendent vertices that enforce list membership. The construction preserves the answer while bounding treedepth plus feedback vertex-set number, yielding W[1]-hardness.
C.1 List enforcement for flipping
- For each forbidden color at an original vertex, the construction adds b + 1 pendent vertices initially colored with that color.The construction uses b = n and is polynomial with the same palette.Source: §C.1 · p. 20, Figure 4 · p. 20
- A proper list coloring extends to a proper coloring of the constructed graph using at most b flips, and any reachable proper coloring within b flips restricts to a proper list coloring.If an original vertex ends with a forbidden color, its b + 1 leaves of that color would all need to be flipped, exceeding the budget.Source: §C.1 · p. 20
- The construction has fvs(H) ≤ k and td(H) + fvs(H) ≤ 2k + 2, establishing W[1]-hardness for treedepth plus feedback vertex set.The reduction starts from the W[1]-hard List Coloring problem of Fiala et al..Source: §C.1 · pp. 20–21
C.2 Reductions from Equitable Coloring
Reductions from Equitable Coloring establish hardness for swapping and sliding under bandwidth or distance-to-disjoint-paths parameters. The constructions preserve equitable color-class sizes and adapt the graph structure to each parameter.
C.2 Reductions from Equitable Coloring
- Arbitrary swaps preserve color-class sizes, so a target coloring is reachable exactly when it is an equitable coloring with the initial histogram.The graph is unchanged, giving hardness for the number of colors plus bandwidth and distance to disjoint paths.Source: §C.2 · p. 21
- Adding a universal vertex yields a distance-to-disjoint-paths reduction, with budgets n for swaps and 3n for slides.The cone uses palette [q + 1], and the modulator grows by at most one; any proper reachable target restricts, after a possible color-name exchange, to an equitable q-coloring.Source: §C.2 · p. 21
- For sliding with bounded bandwidth, the construction connects the graph using a chain of rainbow cliques and component connectors.It sets N = |V(H)| = n(q + 2) and uses slide budget 2N^2.Source: §C.2 · pp. 21–22
- The connected construction admits a proper target with the initial global histogram when G has an equitable coloring, reachable within the stated slide budget.Reachability follows from Lemma 1 and the bound (N − 1)(2 diam(H) − 1) < 2N^2.Source: §C.2 · p. 22
- In every proper target, the cliques consume n copies of each color, leaving G with precisely its initial equitable histogram on [q].Thus restriction to G gives an equitable q-coloring; the bandwidth construction bounds bw(H) by 2(q + 2)(B + 1).Source: §C.2 · p. 22