Faben and Jerrum's homomorphism-counting dichotomy conjecture for graphs
Faben and Jerrum's homomorphism-counting dichotomy conjecture for graphs
Let be a (not necessarily simple) graph. The involution-free reduction of is the lexicographically minimal involution-free graph such that . The problem asks for the number of graph homomorphisms to , modulo .
Faben and Jerrum's conjecture. The problem is in if the involution-free reduction of is the empty graph, a singleton vertex with or without a self-loop, or a graph with two isolated vertices, exactly one of which has a self-loop. Otherwise, it is -complete.
This conjecture proposes a complexity dichotomy for counting graph homomorphisms modulo on arbitrary graphs, extending the known dichotomy for trees. The supplied text does not state whether the conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Andreas Göbel, Leslie Ann Goldberg and David Richerby, “The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2”, arXiv:1307.0556 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.