2 citations · 3 across the 13 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . Combined…
cs.DS2015
Lower Bounds for the Graph Homomorphism Problem
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
The graph homomorphism problem (HOM) asks whether the vertices of a given -vertex graph can be mapped to the vertices of a given -vertex graph such that each edge of…