CaltechAUTHORS
  A Caltech Library Service

A Deterministic Algorithm for Counting Colorings with 2Δ Colors

Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush (2019) A Deterministic Algorithm for Counting Colorings with 2Δ Colors. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 1380-1404. ISBN 9781728149523. https://resolver.caltech.edu/CaltechAUTHORS:20200305-084514309

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200305-084514309

Abstract

We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree Δ, provided only that q ≥ 2Δ. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2.58Δ, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ αΔ+β, where α ≈ 1.764 and β = β(α) are absolute constants. Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/focs.2019.00085DOIArticle
ORCID:
AuthorORCID
Srivastava, Piyush0000-0003-0953-2890
Alternate Title:A Deterministic Algorithm for Counting Colorings with 2-Delta Colors
Additional Information:© 2019 IEEE. JL was a PhD student at UC Berkeley when this work was carried out. Some of this work was carried out while the authors were visiting the Simons Institute for the Theory of Computing. JL and AS were supported by US NSF grant CCF-1815328. PS was supported by a Ramanujan Fellowship of SERB, Indian Department of Science and Technology.
Funders:
Funding AgencyGrant Number
NSFCCF-1815328
Science and Engineering Research Board (SERB)UNSPECIFIED
Department of Science and Technology (India)UNSPECIFIED
Subject Keywords:Approximate counting; Graph coloring; Potts model; Partition function; Stability theory; Derandomization
Record Number:CaltechAUTHORS:20200305-084514309
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200305-084514309
Official Citation:J. Liu, A. Sinclair and P. Srivastava, "A Deterministic Algorithm for Counting Colorings with 2-Delta Colors," 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, USA, 2019, pp. 1380-1404. doi: 10.1109/FOCS.2019.00085
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101721
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:05 Mar 2020 17:11
Last Modified:05 Mar 2020 17:11

Repository Staff Only: item control page