Faben and Jerrum's homomorphism-counting dichotomy conjecture for graphs

Let HH be a (not necessarily simple) graph. The involution-free reduction of HH is the lexicographically minimal involution-free graph HH' such that HHH\rightarrow^* H'. The problem HomsTo(H)\oplus \operatorname{HomsTo}(H) asks for the number of graph homomorphisms to HH, modulo 22.

Faben and Jerrum's conjecture. The problem HomsTo(H)\oplus \operatorname{HomsTo}(H) is in FP\mathrm{FP} if the involution-free reduction of HH 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 P\oplus\mathrm{P}-complete.

This conjecture proposes a complexity dichotomy for counting graph homomorphisms modulo 22 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

Never refreshed

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.