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

About 13 years old · traced to

Let HH be a (not necessarily simple) graph. The involution-free reduction of HH is the lexicographically minimal involution-free graph H′H' such that H→∗H′H\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.

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

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.