Tight lower bounds for list edge coloring

DOI10.4230/LIPICS.SWAT.2018.28MaRDI QIDQ5116492zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Arkadiusz Socała

Publication date 25 August 2020

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

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)

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.

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

Cites work

• A simplified NP-complete satisfiability problem
• Can you beat treewidth?
• List edge and list total colourings of multigraphs
• Narrow sieves for parameterized paths and packings
• On the complexity of k-SAT
• Parameterized algorithms
• Set partitioning via inclusion-exclusion
• The NP-Completeness of Some Edge-Partition Problems
• The list chromatic index of a bipartite multigraph
• Tight lower bounds on graph embedding problems
• Which problems have strongly exponential complexity?

Cited in

(10)

• Lower bounds for monotonic list labeling
• Tight lower bounds for the complexity of multicoloring
• Exact and parameterized algorithms for choosability
• Optimal channel assignment with list-edge coloring
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• Near-optimal list colorings
• 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)