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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problems of counting the homomorphisms, counting the copies, andcounting the induced copies of a $k$-vertex graph $H$ in a $d$-degenerate$n$-vertex graph $G$. Our main result establishes exhaustive and explicitcomplexity classifications for counting subgraphs and induced subgraphs. Weshow that the (not necessarily induced) copies of $H$ in $G$ can be counted intime $f(k,d)\cdot n^{\max(\mathsf{imn}(H),1)}\cdot \log n$, where $f$ is somecomputable function and $\mathsf{imn}(H)$ is the size of the largest inducedmatching of $H$. Whenever the class of allowed patterns has unbounded inducedmatching number, this algorithm is essentially optimal: Unless the ExponentialTime Hypothesis (ETH) fails, there is no algorithm running in time $f(k,d)\cdotn^{o(\mathsf{imn}(H)/\log \mathsf{imn}(H))}$ for any function $f$. In case ofcounting induced subgraphs, we obtain a similar classification along theindependence number $\alpha$: we can count the induced copies of $H$ in $G$ intime $f(k,d)\cdot n^{\alpha(H)}\cdot \log n$, and if the class of allowedpatterns has unbounded independence number, an algorithm running in time$f(k,d)\cdot n^{o(\alpha(H)/\log \alpha(H))}$ is impossible, unless ETH fails.In the language of parameterized complexity, our results yield dichotomies infixed-parameter tractable and $\#\mathsf{W}[1]$-hard cases if we parameterizeby the size of the pattern and the degeneracy of the host graph. Our resultsimply that several patterns cannot be counted in time $f(k,d)\cdot n^{o(k/\logk)}$, including $k$-matchings, $k$-independent sets, (induced) $k$-paths,(induced) $k$-cycles, and induced $(k,k)$-bicliques, unless ETH fails. Thoselower bounds for exact counting are complemented with new algorithms forapproximate counting of subgraphs and induced subgraphs in degenerate graphs.

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies