DocumentCode
2298407
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
fYear
2012
fDate
14-16 May 2012
Firstpage
343
Lastpage
348
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Multiple-Valued Logic (ISMVL), 2012 42nd IEEE International Symposium on
Conference_Location
Victoria, BC
ISSN
0195-623X
Print_ISBN
978-1-4673-0908-0
Type
conf
DOI
10.1109/ISMVL.2012.23
Filename
6214832
Link To Document