Tight lower bounds for list edge coloring

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

Authors: Łukasz Kowalik, Arkadiusz Socała 

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
• Can you beat treewidth?
• 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
• Tight lower bounds on graph embedding problems

Cited In (9)

• Lower bounds for monotonic list labeling
• Tight lower bounds for the complexity of multicoloring
• 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
• Tight lower bounds for the complexity of multicoloring
• 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)