Tight lower bounds for list edge coloring

DOI10.4230/LIPICS.SWAT.2018.28zbMATH Open1477.68235arXiv1804.02537OpenAlexW2964101152MaRDI QIDQ5116492FDOQ5116492

Arkadiusz Socała, Łukasz Kowalik

Publication date: 25 August 2020

Abstract: The fastest algorithms for edge coloring run in time $2^m{n}^{O(1)}$, where $m$ and $n$ are the number of edges and vertices of the input graph, respectively. For dense graphs, this bound becomes $2^{Theta(n^2)}$. This is a somewhat unique situation, since most of the studied graph problems admit algorithms running in time $2^{O(nlogn)}$. It is a notorious open problem to either show an algorithm for edge coloring running in time $2^{o(n^2)}$ or to refute it, assuming Exponential Time Hypothesis (ETH) or other well established assumption. We notice that the same question can be asked for list edge coloring, a well-studied generalization of edge coloring where every edge comes with a set (often called a list) of allowed colors. Our main result states that list edge coloring for simple graphs does not admit an algorithm running in time $2^{o(n^2)}$, unless ETH fails. Interestingly, the algorithm for edge coloring running in time $2^m{n}^{O(1)}$ generalizes to the list version without any asymptotic slow-down. Thus, our lower bound is essentially tight. This also means that in order to design an algorithm running in time $2^{o(n^2)}$ for edge coloring, one has to exploit its special features compared to the list version.

Full work available at URL: https://arxiv.org/abs/1804.02537

Recommendations

• Polynomial time complexity of edge colouring graphs with bounded colour classes
• Improved Edge-Coloring with Three Colors
• List edge multicoloring in graphs with few cycles
• Improved edge-coloring with three colors
• Fast algorithms for edge-coloring planar graphs

zbMATH Keywords

complexitylist edge coloringETH lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• List edge and list total colourings of multigraphs
• Which problems have strongly exponential complexity?
• Narrow sieves for parameterized paths and packings
• Title not available (Why is that?)
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• A simplified NP-complete satisfiability problem
• Set Partitioning via Inclusion-Exclusion
• The list chromatic index of a bipartite multigraph
• The NP-Completeness of Some Edge-Partition Problems
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Tight Lower Bounds on Graph Embedding Problems

Cited In (7)

• Lower bounds for monotonic list labeling
• Optimal channel assignment with list-edge coloring
• Near-optimal list colorings
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• Efficiently list-edge coloring multigraphs asymptotically optimally
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors
• An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

This page was built for publication: Tight lower bounds for list edge coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116492)