1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Perfect Sampling of graph \(k\)-colorings for \(k=o(\Delta^2)\)

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We give an algorithm for perfect sampling from the uniform distribution on proper \(k\)-colorings of graphs of maximum degree \(\Delta\), which, for \(\Delta \in [17, \log n]\), terminates with a sample in expected time \(\mathrm{poly}(n)\) time whenever \(k >\frac{2e\Delta^2}{\log \Delta}\) (here, \(n\) is the number of vertices in the graph). To the best of our knowledge, this is the first perfect sampling algorithm for proper \(k\)-colorings that provably terminates in expected polynomial time while requiring only \(k=o(\Delta^2)\) colors in general. Inspired by the \emph{bounding chain} approach pioneered independently by H\"aggstr\"om \& Nelander~(Scand. J. Statist., 1999) and Huber~(STOC 1998) (who used the approach to give a perfect sampling algorithm requiring \(k >\Delta^2 + 2\Delta\) for its expected running time to be a polynomial), our algorithm is based on a novel bounding chain for the coloring problem.

          Related collections

          Most cited references 6

          • Record: found
          • Abstract: not found
          • Article: not found

          An interruptible algorithm for perfect sampling via Markov chains

           James Fill (1998)
            Bookmark
            • Record: found
            • Abstract: not found
            • Conference Proceedings: not found

            Exact sampling and approximate counting techniques

             Mark Huber (1998)
              Bookmark
              • Record: found
              • Abstract: not found
              • Conference Proceedings: not found

              Uniform sampling through the Lovasz local lemma

                Bookmark

                Author and article information

                Journal
                23 September 2019
                Article
                1909.10323

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                29 pages; 3 figures
                cs.DS cs.DM

                Data structures & Algorithms, Discrete mathematics & Graph theory

                Comments

                Comment on this article