ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let HH be a graph. An involution-free reduction of HH is the unique, up to isomorphism, involution-free graph H∗H^* such that H⇒∗H∗H\Rightarrow^* H^*, where H⇒∗H′H\Rightarrow^* H' denotes a sequence of reductions by taking the subgraph induced by the fixed points of a nontrivial involutive automorphism, up to isomorphism. Write ⊕HomsTo⁡(H)\oplus\operatorname{HomsTo}(H) for the problem of counting homomorphisms from an input graph to HH, modulo 22.

Faben–Jerrum's conjecture. Let HH be a graph. If its involution-free reduction H∗H^* has at most one vertex, then ⊕HomsTo⁡(H)\oplus\operatorname{HomsTo}(H) is in P\mathrm{P}; otherwise, ⊕HomsTo⁡(H)\oplus\operatorname{HomsTo}(H) is ⊕P\oplus\mathrm{P}-complete.

This conjecture predicts a complete polynomial-time versus ⊕P\oplus\mathrm{P}-complete dichotomy for counting graph homomorphisms modulo 22. 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.