Counting homomorphisms to K4-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 prob...
| Autores principales: | , , , |
|---|---|
| Formato: | Conference item |
| Lenguaje: | English |
| Publicado: |
Society for Industrial and Applied Mathematics
2021
|