Journal article icon

Journal article

The complexity of approximately counting retractions

Abstract:

Let G be a graph that contains an induced subgraph H. A retraction from G to H is a homomorphism from G to H that is the identity function on H. Retractions are very well studied: Given H, the complexity of deciding whether there is a retraction from an input graph G to H is completely classified, in the sense that it is known for which H this problem is tractable (assuming P ≠ NP). Similarly, the complexity of (exactly) counting retractions from G to H is classified (assuming FP ≠ #P). Howev...

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

Actions


Access Document


Files:
Publisher copy:
10.1145/3397472

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
New College
Role:
Author
ORCID:
0000-0002-6895-755X
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0003-1879-6089
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Jesus College
Role:
Author
Publisher:
Association for Computing Machinery Publisher's website
Journal:
ACM Transactions on Computation Theory Journal website
Volume:
12
Issue:
3
Article number:
15
Pages:
15:1 - 15:43
Publication date:
2020-06-01
Acceptance date:
2020-03-01
DOI:
EISSN:
1942-3462
ISSN:
1942-3454
Language:
English
Keywords:
Pubs id:
1097344
Local pid:
pubs:1097344
Deposit date:
2020-03-29

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