English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the problem of counting all $k$-vertex subgraphs in an inputgraph, for any constant $k$. This problem (denoted sub-cnt$_k$) has beenstudied extensively in both theory and practice. In a classic result, Chiba andNishizeki (SICOMP 85) gave linear time algorithms for clique and 4-cyclecounting for bounded degeneracy graphs. This is a rich class of sparse graphsthat contains, for example, all minor-free families and preferential attachmentgraphs. The techniques from this result have inspired a number of recentpractical algorithms for sub-cnt$_k$. Towards a better understanding of thelimits of these techniques, we ask: for what values of $k$ can sub-cnt$_k$ besolved 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 infine-grained complexity, we prove that for all $k \geq 6$, sub-cnt$_k$ cannotbe solved even in near-linear time.

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