Counting Program Seminar Series

Lower Bounds on Graph Homomorphism

We discuss conditional (subject to Exponential Time Hypothesis) lower bound on solving Graph Homomorphism exactly. This bound can be used to obtain lower bounds for various graph embedding problems including Subgraph Isomorphism, Graph Minors, etc.
Based on a joint work with Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin and Marek Cygan, Jakub Pachocki, Arkadiusz Socala