Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The complexity of the list homomorphism problem for graphs
Egri L., Krokhin A., Larose B., Tesson P. Theory of Computing Systems51 (2):143-178,2012.Type:Article
Date Reviewed: May 8 2013

Homomorphisms are very useful in combinatorial problems in mapping and assignments. Homomorphism problems involve greater modeling power than graph coloring, yet compared to general constraint satisfaction problems (CSPs), they are simple and easy to manage. Identifying the complexity of the list H-coloring problem for graphs is important when it comes to some statistical applications in physics, as well as the study of CSPs.

The authors categorize the computational complexities of the list H-coloring problem for graphs. The paper contains an extensive literature review of several theories with their complexity analysis. The authors analyze the related methods and present an extensive analysis of the conditions of the tame congruence theory algebraic framework. For undirected graphs without loops, a homomorphism to a complete graph K is an n-coloring [1]. The authors use the tame congruence theory to prove that the algebraic conditions used in the theory are sufficient and vital in list H-coloring for undirected graphs with loops.

The authors use the right methodologies to show two equivalent characterizations of graphs H such that they are L-hard. The first characterization is done with reflexive graphs, and the other is constructed with an inductive method. The first characterization has been used to prove that graphs outside of the reflexive graphs class cause NL-hard problems. The authors show this by constructing non-Boolean types of algebras associated with the graphs; several lemmas are presented. The inductive method is used to give positive results. The authors use this inductive definition to show that the negative instances of CSP are definable in symmetric Datalog, and thus show the CSP in L.

Each lemma in the paper is carefully constructed, with detailed proofs and necessary explanations. The authors clearly classify the complexities to be L-complete, NL-complete, NP-complete, or first-order definable. The paper is well written, theoretically sound, and fundamental. I found it very interesting.

Reviewer:  Ganapathy Mani Review #: CR141209 (1308-0723)
1) Hell, P. Surveys in combinatorics 2003London Mathematical Society Lecture Note Series 307: London Mathematical Society Lecture Note Series 307. Cambridge University Press, , 2003.
Bookmark and Share
 
Complexity Measures And Classes (F.1.3 )
 
 
Logic And Constraint Programming (F.4.1 ... )
 
 
Combinatorics (G.2.1 )
 
 
General (I.1.0 )
 
 
Graph Theory (G.2.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