DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2020.38

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

Authors: Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract

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 and practice. In a classic result, Chiba and Nishizeki (SICOMP 85) gave linear time algorithms for clique and 4-cycle counting for bounded degeneracy graphs. This is a rich class of sparse graphs that contains, for example, all minor-free families and preferential attachment graphs. The techniques from this result have inspired a number of recent practical algorithms for SUB-CNT_k. Towards a better understanding of the limits of these techniques, we ask: for what values of k can SUB_CNT_k be solved in linear time? We discover a chasm at k=6. Specifically, we prove that for k < 6, SUB_CNT_k can be solved in linear time. Assuming a standard conjecture in fine-grained complexity, we prove that for all k ⩾ 6, SUB-CNT_k cannot be solved even in near-linear time.

Cite as

Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.ITCS.2020.38,
  author =	{Bera, Suman K. and Pashanasangi, Noujan and Seshadhri, C.},
  title =	{{Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.38},
  URN =		{urn:nbn:de:0030-drops-117239},
  doi =		{10.4230/LIPIcs.ITCS.2020.38},
  annote =	{Keywords: Subgraph counting, bounded degeneracy graphs, fine-grained complexity}
}

Search Results

Documents authored by Pashanasangi, Noujan

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

Abstract

Cite as

Thanks for your feedback!

Could not send message