C. Seshadhri

A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs

Subgraph and homomorphism counting are fundamental algorithmic problems. Given a constant-size pattern graph H and a large input graph G , we wish to count the number of H -homomorphisms/subgraphs in G . Given the massive sizes of real-world graphs and the practical importance of...