TY - GEN

T1 - On the algorithmic Lovász local lemma and acyclic edge coloring

AU - Giotis, Ioannis

AU - Kirousis, Lefteris

AU - Psaromiligkos, Kostas I.

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Copyright (2015) by SIAM: Society for Industrial and Applied Mathematics. All rights reserved.

PY - 2015

Y1 - 2015

N2 - The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most [3.74(Δ - 1)] + 1 colors, whereas the previously known best bound was 4(Δ - 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the "undesirable" events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovász Local Lemma.

AB - The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most [3.74(Δ - 1)] + 1 colors, whereas the previously known best bound was 4(Δ - 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the "undesirable" events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovász Local Lemma.

UR - http://www.scopus.com/inward/record.url?scp=84959888542&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959888542&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84959888542

T3 - 12th Workshop on Analytic Algorithmics and Combinatorics 2015, ANALCO 2015

SP - 16

EP - 25

BT - 12th Workshop on Analytic Algorithmics and Combinatorics 2015, ANALCO 2015

PB - Society for Industrial and Applied Mathematics Publications

T2 - 12th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015

Y2 - 4 January 2015

ER -