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.
References
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
No solutions have been posted yet.