2026-07-31T13:45:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8854 2024-03-06T10:42:48Z ddc:004 open_access

Tight Lower Bounds for List Edge Coloring Kowalik, Lukasz Socala, Arkadiusz list edge coloring complexity ETH lower bound 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukasz Kowalik and Arkadiusz Socala 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.28 urn:nbn:de:0030-drops-88540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.28 eng https://creativecommons.org/licenses/by/3.0/legalcode