Proper vertex coloring through edge weights improved by vertex cover parameter
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
Summary
The authors study a way to color the nodes of a graph based on the weights assigned to connecting edges, ensuring neighboring nodes have different totals. They focus on cases where weights come from just two numbers and prove it’s very hard to decide if such a coloring exists in general. However, they show that if the graph has a small vertex cover (a set of nodes touching all edges), they can simplify the problem significantly and solve it efficiently. This work extends to situations where some edges already have fixed weights and explores other graph properties where solving remains difficult.
What this means in practice
- •For network schedulers: Optimize channel assignment with simplified problem kernels when key network nodes form small vertex covers.
- •For circuit designers: Design circuits with constraints modeled by edge-weighted vertex colorings, exploiting efficient solutions when vertex cover size is small.
Authors
Shubhada Aute, Fahad Panolan, Geevarghese Philip
Abstract
An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.