Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six

Suman K. Bera, Noujan Pashanasangi, C. Seshadhri

We consider the problem of counting all $k$-vertex subgraphs in an input graph, for any constant $k$. This problem (denoted sub-cnt${}_k$) has been studied extensively in both theory…