Journal article icon

Journal article

Counting homomorphisms to K4-minor-free graphs, modulo 2

Abstract:

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 [Theory Comput., 11 (2015), pp. 35--57] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class $\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertic...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/20M1382921

Authors


More by this author
Institution:
University of Oxford
Department:
COMPUTER SCIENCE
Sub department:
Computer Science
Role:
Author
ORCID:
0000-0003-1879-6089
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Discrete Mathematics Journal website
Volume:
35
Issue:
4
Pages:
2749–2814
Publication date:
2021-11-18
Acceptance date:
2021-07-26
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
Language:
English
Keywords:
Pubs id:
1187641
Local pid:
pubs:1187641
Deposit date:
2021-07-27

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP