On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The algorithm for Lov\'{a}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. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree $\Delta$ has an acyclic proper edge coloring with at most $\lceil 3.74(\Delta-1)\rceil+1$ colors, whereas the previously known best bound was $4(\Delta-1)$. The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of the latter 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\'{a}sz Local Lemma.
Type de document :
Communication dans un congrès
ANALCO: Analytic Algorithmics and Combinatorics, Jan 2015, San Diego, California, United States. 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). 〈http://www.siam.org/meetings/analco15/〉. 〈10.1137/1.9781611973761.2〉

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225505
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 6 novembre 2015 - 11:30:54
Dernière modification le : vendredi 5 octobre 2018 - 21:14:01

Citation

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos. On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring. ANALCO: Analytic Algorithmics and Combinatorics, Jan 2015, San Diego, California, United States. 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). 〈http://www.siam.org/meetings/analco15/〉. 〈10.1137/1.9781611973761.2〉. 〈lirmm-01225505〉

Métriques

Consultations de la notice