Faben–Jerrum dichotomy conjecture for homomorphisms to graphs modulo 2
Statement
Let be a graph. An involution-free reduction of is the unique, up to isomorphism, involution-free graph such that , where denotes a sequence of reductions by taking the subgraph induced by the fixed points of a nontrivial involutive automorphism, up to isomorphism. Write for the problem of counting homomorphisms from an input graph to , modulo .
Faben–Jerrum's conjecture. Let be a graph. If its involution-free reduction has at most one vertex, then is in ; otherwise, is -complete.
This conjecture predicts a complete polynomial-time versus -complete dichotomy for counting graph homomorphisms modulo . Faben and Jerrum established the existence and uniqueness of the involution-free reduction; the dichotomy asserted here is the remaining complexity classification.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.