Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2

We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the pro...

Descripción completa

Detalles Bibliográficos

Autores principales:	Focke, Jacob, Goldberg, Leslie Ann, Roth, Marc, Živný, Stanislav
Formato:	Artículo
Publicado:	2020
Materias:	Computational Complexity Discrete Mathematics F.2.2; G.2.1
Acceso en línea:	https://arxiv.org/abs/2006.16632 http://arxiv.org/abs/2006.16632
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!