License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.28
URN: urn:nbn:de:0030-drops-88540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8854/
Go to the corresponding LIPIcs Volume Portal

Kowalik, Lukasz ; Socala, Arkadiusz

Tight Lower Bounds for List Edge Coloring

pdf-format:
LIPIcs-SWAT-2018-28.pdf (0.5 MB)

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(n log n)}. 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 the Exponential Time Hypothesis (ETH) or other well established assumptions.
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.

BibTeX - Entry

@InProceedings{kowalik_et_al:LIPIcs:2018:8854,
  author =	{Lukasz Kowalik and Arkadiusz Socala},
  title =	{{Tight Lower Bounds for List Edge Coloring}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8854},
  URN =		{urn:nbn:de:0030-drops-88540},
  doi =		{10.4230/LIPIcs.SWAT.2018.28},
  annote =	{Keywords: list edge coloring, complexity, ETH lower bound}
}

Keywords: list edge coloring, complexity, ETH lower bound
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI