Improved method for testing if large graphs need many changes to be k-colorable
Near-Optimal Bounds for Testing k-Colorability
Discrete Mathematics
Summary
The paper looks at how to quickly check if a large network can be colored with k colors so that no connected nodes share the same color, or if it is very far from this possibility. The authors found a way to test this by examining a small random part of the network, whose size depends on k and the allowed error, ε. Their method is as efficient as possible in the relationship with ε and slightly better than previous methods for certain parameter ranges. They introduced a new coloring process to prove this result.
What this means in practice
- •For graph algorithm developers: Use the improved bounds to design more efficient algorithms that quickly test graph colorability in large networks.
- •For network optimization engineers: Estimate how close a communication network is to being k-colorable based on small samples, aiding efficient resource allocation.
A theory result. No direct application yet.
Authors
Bangjie Xu
Abstract
We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that, for every integer $k\ge 2$, a uniformly random induced subgraph on \[ O\!\left(\frac{k\log k}{\varepsilon}\right) \] vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof introduces a trial coloring process based on nested palette systems and iteratively selected pivots. This yields an upper bound of $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log(1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement whenever $1/\varepsilon$ is superpolynomial in $k$. Moreover, for every fixed $k$, our bound matches the known lower bound, thereby establishing the optimal $Θ(1/\varepsilon)$ dependence on $\varepsilon$ and, to the best of our knowledge, achieving this optimal dependence for the first time.