Fedor Fomin (University of Bergen)
Calvin Lab Room 116
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