2019/11/13 by Suman K. Bera, Bera, Suman K., Noujan Pashanasangi +3 · 5 citations
Computer Science · Materials Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Nanocluster Synthesis and Applications
paper · pdf · doi:10.48550/arxiv.1911.05896
openalex publication_date 2019/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of counting all k-vertex subgraphs in an input\ngraph, for any constant k. This problem (denoted sub-cntk) has been\nstudied extensively in both theory and practice. In a classic result, Chiba and\nNishizeki (SICOMP 85) gave linear time algorithms for clique and 4-cycle\ncounting for bounded degeneracy graphs. This is a rich class of sparse graphs\nthat contains, for example, all minor-free families and preferential attachment\ngraphs. The techniques from this result have inspired a number of recent\npractical algorithms for sub-cntk. Towards a better understanding of the\nlimits of these techniques, we ask: for what values of k can sub-cntk be\nsolved in linear time?\n We discover a chasm at k=6. Specifically, we prove that for k < 6,\nsub-cntk can be solved in linear time. Assuming a standard conjecture in\nfine-grained complexity, we prove that for all k \≥ 6, sub-cntk cannot\nbe solved even in near-linear time.\n