Faster Edge Coloring by Partition Sieving

Shyan Akmal, Tomohiro Koana · 2025

Read Faster Edge Coloring by Partition Sieving by Shyan Akmal, Tomohiro Koana (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05570.txt.

Introduction

Shyan Akmal and Tomohiro Koana wrote this 2025 computer science paper on the edge coloring problem. In that problem, each edge of a graph gets a color so that no two edges at the same vertex share a color. The goal is to use as few colors as possible, and the problem is known to be NP-hard.

Earlier exact methods either took about two to the power m steps, where m is the edge count, or used a huge amount of memory. The authors give a new algorithm that runs faster and uses only modest, polynomial space. Their method is the first to gain both wins at once. The gain comes from a technique they call partition sieving, which sorts cases into groups and rules out whole groups at a time.

Catalog record

CREATORShyan Akmal, Tomohiro Koana
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05570

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Faster Edge Coloring by Partition Sieving Shyan Akmal, Tomohiro Koana Abstract In the Edge Coloring problem, we are given an undirected graph G G with n n vertices and m m edges, and are tasked with finding the smallest positive integer k k so that the edges of G G can be assigned k 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 ​ poly ⁡ ( n ) 2^{m}\poly(n) time and polynomial space, and in graphs with average degree d d in 2 ( 1 − ε d ) ​ m ​ poly ⁡ ( n ) 2^{(1-\varepsilon_{d})m}\poly(n) time and exponential space, where ε d = ( 1 / d ) Θ ⁡ ( d 3 ) \varepsilon_{d}=(1/d)^{\Theta(d^{3})} . We present an algorithm that solves Edge Coloring in 2 m − 3 ​ n / 5 ​ poly ⁡ ( n ) 2^{m-3n/5}\poly(n) time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than 2 m ​ poly ⁡ ( m ) 2^{m}\poly(m) time and uses only polynomial space. In graphs of average degree d d , our algorithm runs in 2 ( 1 − 6 / ( 5 ​ d ) ) ​ m ​ poly ⁡ ( n ) 2^{(1-6/(5d))m}\poly(n) time, which has far better dependence in d d than previous results. We also consider a generalization of Edge Coloring called List Edge Coloring , where each edge e e in the input graph comes with a list L e ⊆ { 1 , … , k } 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 show that this problem can be solved in 2 ( 1 − 6 / ( 5 ​ k ) ) ​ m ​ poly ⁡ ( n ) 2^{(1-6/(5k))m}\poly(n) time and polynomial space. The previous best algorithm for List Edge Coloring took 2 m ​ poly ⁡ ( n ) 2^{m}\poly(n) time and space. Our algorithms are algebraic, and work by constructing a special polynomial P P based off the input graph that contains a multilinear monomial (i.e., a monomial where every variable has degree at most one) if and only if the answer to the List Edge Coloring problem on the input graph is YES. We then solve the problem by detecting multilinear monomials in P P . Previous work also employed such monomial detection techniques to solve Edge Coloring . We obtain faster algorithms both by carefully constructing our polynomial P P , and by improving the runtimes for certain structured monomial detection problems using a technique we call partition sieving. INSAIT, Sofia University “St. Kliment Ohridski”, Bulgaria and https://www.shyan.akmal.com [email protected]://orcid.org/0000-0002-7266-2041Partially funded by the Ministry of Education and Science of Bulgaria (support for INSAIT, part of the Bulgarian National Roadmap for Research Infrastructure).Technische Universität Berlin, Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexitytomohiro.koana@tu-berlin.de0000-0002-8684-0611Supported by the DFG Project DiPa, NI 369/21. We thank the anonymous reviewers for helpful feedback on this work. keywords coloring, edge coloring, chromatic index, matroid, pfaffian, algebraic algorithm ccs Theory of computation Graph algorithms analysis ccs Theory of computation Parameterized complexity and exact algorithms † † runningauthor: S. Akmal and T. Koana † † copyright: Shyan Akmal and Tomohiro Koana 1 Introduction Coloring graphs is a rich area of research in graph theory and computer science. Given a graph G , a proper vertex coloring of G is an assignment of colors to its nodes such that no two adjacent vertices receive the same color. In the Vertex Coloring problem, we are given an undirected graph G on n vertices, and are tasked with computing the smallest positive integer k such that G admits a proper vertex coloring using k colors. Vertex Coloring is a classic combinatorial problem, NP -hard to solve even approximately [ 34 ] . An influential line of research has worked on designing faster and faster exponential-time algorithms for this problem [ 30 , 19 , 14 , 9 ] , culminating in an algorithm solving Vertex Coloring in O^{*}(2^{n}) time and space [ 12 ] , where throughout we write O^{*}(f(n)) as shorthand for f(n)\poly(n) . In this paper, we study exact algorithms for the closely related Edge Coloring problem. Given a graph G , a proper edge coloring of G is an assignment of colors to its edges such that no two edges incident to a common vertex receive the same color. The smallest positive integer k such that G admits a proper edge coloring using k colors is the chromatic index of G , denoted by \chi^{\prime}(G) . In the Edge Coloring problem, we are given an undirected graph G on n vertices and m edges, and are tasked with computing \chi^{\prime}(G) . Let \Delta denote the maximum degree of the input graph G . For each vertex v in G , a proper edge coloring of G must assign distinct colors to the edges incident to v . Thus \chi^{\prime}(G)\geq\Delta . A classic result in graph theory known as Vizing’s theorem proves that in fact \chi^{\prime}(G)\leq\Delta+1 , so that the simple \Delta lower bound is close to the truth. Moreover, a proper edge coloring of G using (\Delta+1) colors can be found in near-linear time [ 2 ] . Consequently, solving Edge Coloring amounts to distinguishing between the cases \chi^{\prime}(G)=\Delta and \chi^{\prime}(G)=\Delta+1 . Despite this powerful structural result, the Edge Coloring problem is NP -hard just like Vertex Coloring , even for graphs where all vertices have degree exactly \Delta=3 [ 24 ] . In recent years, researchers have made major strides in our knowledge of algorithms for approximate variants of Edge Coloring in the distributed [ 22 , 5 , 3 ] and dynamic settings [ 17 , 15 , 6 ] . In comparison, much less is known about the exponential-time complexity for solving the Edge Coloring problem exactly . A simple way to solve Edge Coloring is by reduction to Vertex Coloring . Given the input graph G , we can construct in polynomial time the line graph L(G) whose nodes are edges of G , and whose nodes are adjacent if the corresponding edges in G are incident to a common vertex. By construction, the solution to Vertex Coloring on L(G) gives the solution to Edge Coloring on G . If G has m edges and maximum degree \Delta , then L(G) has m vertices and maximum degree (2\Delta-1) . Using the aforementioned O^{*}(2^{n}) time and space algorithm for Vertex Coloring , this immediately implies a O^{*}(2^{m}) time and space algorithm for Edge Coloring . In graphs with maximum degree \Delta , Vertex Coloring can be solved in O^{*}(2^{(1-\varepsilon)n}) time and space, where \varepsilon=(1/2)^{\Theta(\Delta)} [ 10 ] . By applying the above reduction, Edge Coloring

Read the complete text