On the Complexity of Approximately Counting Retractions

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). In some recent work, we study the complexity of approximately counting retractions and arrive at a complete complexity trichotomy for all square-free graphs H.

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.