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

Given a graph property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ asks, oninput a graph $G$ and a positive integer $k$, to compute the number of inducedsubgraphs of size $k$ in $G$ that satisfy $\Phi$. The search for explicitcriteria on $\Phi$ ensuring that $\#\mathsf{IndSub}(\Phi)$ is hard wasinitiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of themajor line of research on counting small patterns in graphs. However, apartfrom an implicit result due to Curticapean, Dell and Marx [STOC 17] provingthat a full classification into "easy" and "hard" properties is possible andsome partial results on edge-monotone properties due to Meeks [Discret. Appl.Math. 16] and D\"orfler et al. [MFCS 19], not much is known.  In this work, we fully answer and explicitly classify the case of monotone,that is subgraph-closed, properties: We show that for any non-trivial monotoneproperty $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ cannot be solved in time$f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless theExponential Time Hypothesis fails. By this, we establish that any significantimprovement over the brute-force approach is unlikely; in the language ofparameterized complexity, we also obtain a $\#\mathsf{W}[1]$-completenessresult.

Counting Small Induced Subgraphs Satisfying Monotone Properties