Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.38
URN: urn:nbn:de:0030-drops-117239
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11723/
Bera, Suman K. ; Pashanasangi, Noujan ; Seshadhri, C.
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{bera_et_al:LIPIcs:2020:11723,
author = {Suman K. Bera and Noujan Pashanasangi and C. Seshadhri},
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 = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11723},
URN = {urn:nbn:de:0030-drops-117239},
doi = {10.4230/LIPIcs.ITCS.2020.38},
annote = {Keywords: Subgraph counting, bounded degeneracy graphs, fine-grained complexity}
}
| Keywords: | Subgraph counting, bounded degeneracy graphs, fine-grained complexity | |
| Seminar: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 06.01.2020 |
