Journal article icon

Journal article

Counting homomorphisms to square-free graphs, modulo 2

Abstract:

We study the problem HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph H. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting, so subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4-cycles, HomsToH is either in polynomial time or is P-complete. This partially confirms a conjecture of Faben and J...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1145/2898441

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Journal:
ACM Transactions on Computation Theory Journal website
Volume:
8
Issue:
3
Pages:
12
DOI:
EISSN:
1942-3462
ISSN:
1942-3454
URN:
uuid:0dd1c6c8-5e47-4c22-b574-f5662f821a3b
Source identifiers:
588398
Local pid:
pubs:588398

Terms of use


Metrics


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