Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A complexity trichotomy for approximately counting list H-colorings
Galanis A., Goldberg L., Jerrum M. ACM Transactions on Computation Theory9 (2):1-22,2017.Type:Article
Date Reviewed: Jan 11 2018

H-colorings are essential in the exploration of language syntax expositions. An H-coloring is the allocation of adjacent colors to neighboring vertices of a graph G. An H-coloring is a homomorphism mapping of a graph G to H. Even though the computational intricacy for calculating the precise solutions to count the lists of H-colorings exists in the literature, questions remains as to how the approximate count should be derived. Galanis and colleagues present a complexity trichotomy for practically enumerating the H-colorings of a graph.

A fully polynomial randomized approximation scheme is a randomized technique for generating foreseeable problem solutions within a definite comparative error, with high likelihood in polynomial time. An approximate preserving reduction is a randomized Turing reduction for computing close solution approximations of a problem, given the close approximations of any other problem. #SAT is the enumeration problem that satisfies the assignments of a Boolean formula. #BIS is the problem of enumerating autonomous sets in a bipartite graph.

Given a connected undirected loop-free or circling graph H, the complexity trichotomy creators theorized and verified that (1) for a reflexive all-inclusive or an irreflexive two-part graph H and a graph G with utmost degree vertices, the H-colorings can be enumerated in polynomial time, and (2) for a reflexive appropriate interval or an irreflexive two-part permutation graph H and a graph G with highest degree vertices of at least six, the H-colorings enumeration can be approximated from the autonomous sets in a bipartite graph.

The authors convincingly state and prove lemmas for #SAT-equivalent, #BIS-hard, and #BIS-easy problems that were used to ascertain the complexity trichotomy theorems. They skillfully use matrix algebra and examples of irreflexive non-bipartite permutation graphs and reflexive improper interval graphs to illuminate the proofs of the lemmas for approximately counting the list of H-colorings.

I strongly recommend that all researchers in the areas of formal languages and theory of computing read the insightful approaches to the proofs of lemmas and theorems in this paper.

Reviewer:  Amos Olagunju Review #: CR145765 (1803-0153)
Bookmark and Share
  Featured Reviewer  
 
Complexity Measures And Classes (F.1.3 )
 
 
Discrete Mathematics (G.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Complexity Measures And Classes": Date
Nonuniform proof systems
Kämper J. Theoretical Computer Science 85(2): 305-331, 1991. Type: Article
Feb 1 1993
Reversal complexity
Chen J., Yap C. SIAM Journal on Computing 20(4): 622-638, 1991. Type: Article
Oct 1 1992
Lower bounds for algebraic computation trees with integer inputs
Yao A. (ed) SIAM Journal on Computing 20(4): 655-668, 1991. Type: Article
Jul 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy