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 problem #IndSub(P) of counting all induced subgraphs of size kin a graph G that satisfy the property P. This problem was introduced by Jerrumand Meeks and shown to be #W[1]-hard when parameterized by k for some familiesof properties P including, among others, connectivity [JCSS 15] and even- oroddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], twoof the authors introduced a novel technique for the complexity analysis of#IndSub(P), inspired by the "topological approach to evasiveness" of Kahn, Saksand Sturtevant [FOCS 83] and the framework of graph motif parameters due toCurticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a widerange of properties P. In this work, we refine this technique for graphproperties that are non-trivial on edge-transitive graphs with a prime powernumber of edges. In particular, we fully classify the case of monotonebipartite graph properties: It is shown that, given any graph property P thatis closed under the removal of vertices and edges, and that is non-trivial forbipartite graphs, the problem #IndSub(P) is #W[1]-hard and cannot be solved intime f(k)*n^{o(k)} for any computable function f, unless the Exponential TimeHypothesis fails. This holds true even if the input graph is restricted to bebipartite and counting is done modulo a fixed prime. A similar result is shownfor properties that are closed under the removal of edges only.

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness