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 introduce a class of parameterised counting problems on graphs, p-#InducedSubgraph With Property(\Phi), which generalises a number of problems which havepreviously been studied. This paper focusses on the case in which \Phi definesa family of graphs whose edge-minimal elements all have bounded treewidth; thisincludes the special case in which \Phi describes the property of beingconnected. We show that exactly counting the number of connected inducedk-vertex subgraphs in an n-vertex graph is #W[1]-hard, but on the other handthere exists an FPTRAS for the problem; more generally, we show that thereexists an FPTRAS for p-#Induced Subgraph With Property(\Phi) whenever \Phi ismonotone and all the minimal graphs satisfying \Phi have bounded treewidth. Wethen apply these results to a counting version of the Graph Motif problem.

The Parameterised Complexity of Counting Connected Subgraphs and Graph Motifs