Weighted edge coloring matches local packing in large graphs
Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
Discrete MathematicsData Structures and Algorithms
Summary
The paper studies how to color the edges of a graph when each edge has a weight, so that no vertex carries too much weight of the same color. The authors show that by carefully combining local packing solutions, it is possible to color almost optimally, using about as many colors as suggested by easy-to-compute local limits. This solves a longstanding question and also disproves a previous conjecture about exact weighting. They provide efficient algorithms and formalize the proofs in a computer system.
What this means in practice
- •For network schedulers: Optimize resource allocation with weighted tasks by coordinating local constraints into globally efficient scheduling patterns.
- •For operations researchers: Use asymptotic weighted edge coloring bounds to improve approximation algorithms for complex packing and scheduling problems.
Authors
Rishikesh Gajjala, Arindam Khan
Abstract
We study weighted edge coloring, where each edge of a graph $G$ has a weight in $(0,1]$, and colors are assigned so that the incident weight of each color at every vertex is at most one. The objective is to minimize the number of colors, denoted by $χ'_w(G)$. This generalizes classical edge coloring (all weights are one) and bin packing ($G$ is a star). Two natural lower bounds are the maximum weighted degree $Δ_w(G)$ and the maximum local bin-packing number $\mathrm{bp}(G)$: the maximum, over vertices, of the minimum number of unit bins needed to pack the incident weights. We have $\lceilΔ_w(G)\rceil\le\mathrm{bp}(G)\leχ'_w(G)$. How closely these local lower bounds approximate the global optimum is a longstanding open problem. Our main result establishes an asymptotic weighted analogue of Vizing's theorem: every simple graph admits a coloring using at most $(1+o(1))\mathrm{bp}(G)$ colors. Thus local bin packings can be made globally consistent with asymptotically vanishing relative loss, even in nonbipartite graphs. Our local-to-global rounding framework coordinates feasible local packing distributions into a partial coloring, leaving only $o(\mathrm{bp}(G))$ uncolored weight at every vertex. For bipartite multigraphs, we prove $χ'_w(G)\le(2+o(1))Δ_w(G)$, establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound $χ'_w(G)\le3\lceilΔ_w(G)\rceil$. Both leading coefficients are optimal, giving weighted analogues of the classical Kőnig--Shannon bounds. Further upper and lower bounds show that the classical factor-$3/2$ separation does not persist with the local bin-packing benchmark. We also disprove the exact weighted-degree conjecture of Feige and Singh [ESA'08]. Our upper bounds have polynomial-time algorithms, and their existence statements are formalized in Lean 4.