Faster Edge Coloring by Partition Sieving
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909453147701248 |
|---|---|
| author | Akmal, Shyan Koana, Tomohiro |
| author_facet | Akmal, Shyan Koana, Tomohiro |
| contents | In the Edge Coloring problem, we are given an undirected graph $G$ with $n$ vertices and $m$ edges, and are tasked with finding the smallest positive integer $k$ so that the edges of $G$ can be assigned $k$ colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in $2^m\text{poly}(n)$ time and polynomial space, and in graphs with average degree $d$ in $2^{(1-\varepsilon_d)m}\text{poly}(n)$ time and exponential space, where $\varepsilon_d = (1/d)^{Θ(d^3)}$.
We present an algorithm that solves Edge Coloring in $2^{m-3n/5}\text{poly}(n)$ time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than $2^m\text{poly}(m)$ time and uses only polynomial space. In graphs of average degree $d$, our algorithm runs in $2^{(1-6/(5d))m}\text{poly}(n)$ time, which has far better dependence in $d$ than previous results. We also generalize our algorithm to solve a problem known as List Edge Coloring, where each edge $e$ in the input graph comes with a list $L_e\subseteq\left\{1, \dots, k\right\}$ of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We solve this problem in $2^{(1-6/(5k))m}\text{poly}(n)$ time and polynomial space. The previous best algorithm for List Edge Coloring took $2^m\text{poly}(n)$ time and space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05570 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Edge Coloring by Partition Sieving Akmal, Shyan Koana, Tomohiro Data Structures and Algorithms In the Edge Coloring problem, we are given an undirected graph $G$ with $n$ vertices and $m$ edges, and are tasked with finding the smallest positive integer $k$ so that the edges of $G$ can be assigned $k$ colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in $2^m\text{poly}(n)$ time and polynomial space, and in graphs with average degree $d$ in $2^{(1-\varepsilon_d)m}\text{poly}(n)$ time and exponential space, where $\varepsilon_d = (1/d)^{Θ(d^3)}$. We present an algorithm that solves Edge Coloring in $2^{m-3n/5}\text{poly}(n)$ time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than $2^m\text{poly}(m)$ time and uses only polynomial space. In graphs of average degree $d$, our algorithm runs in $2^{(1-6/(5d))m}\text{poly}(n)$ time, which has far better dependence in $d$ than previous results. We also generalize our algorithm to solve a problem known as List Edge Coloring, where each edge $e$ in the input graph comes with a list $L_e\subseteq\left\{1, \dots, k\right\}$ of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We solve this problem in $2^{(1-6/(5k))m}\text{poly}(n)$ time and polynomial space. The previous best algorithm for List Edge Coloring took $2^m\text{poly}(n)$ time and space. |
| title | Faster Edge Coloring by Partition Sieving |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.05570 |