Title :
List-Homomorphism Problems on Graphs and Arc Consistency
Author :
Larose, Benoit ; Lemaitre, Adrien
Author_Institution :
Dept. of Math. & Stat., Concordia Univ., Montreal, QC, Canada
Abstract :
We characterise the graphs (which may contain loops) whose list-homomorphism problem is solvable by arc consistency, or equivalently, that admit conservative totally symmetric idempotent operations of all arities. We prove that for every bipartite graph G, its list-homomorphism problem is tractable if and only if G admits a monochromatic conservative semi lattice operation, in particular, its list-homomorphism problem can easily be solved by a combination of two-colouring and arc-consistency.
Keywords :
computational complexity; constraint satisfaction problems; graph theory; arc consistency; bipartite graph; list-homomorphism problem; monochromatic conservative semilattice operation; symmetric idempotent operation; two-colouring; Algebra; Bipartite graph; Color; Complexity theory; Partitioning algorithms; Periodic structures; Standards; List-homomorphism problems; arc-consistency; graphs; symmetric Datalog; totally symmetric operations;
Conference_Titel :
Multiple-Valued Logic (ISMVL), 2012 42nd IEEE International Symposium on
Conference_Location :
Victoria, BC
Print_ISBN :
978-1-4673-0908-0
DOI :
10.1109/ISMVL.2012.23
