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 consider the problem of counting, in a given graph, the number of inducedk-vertex subgraphs which have an even number of edges, and also thecomplementary problem of counting the k-vertex induced subgraphs having an oddnumber of edges. We demonstrate that both problems are #W[1]-hard whenparameterised by k, in fact proving a somewhat stronger result about countingsubgraphs with a property that only holds for some subset of k-vertex subgraphswhich have an even (respectively odd) number of edges. On the other hand, weshow that the problems of counting even and odd k-vertex induced subgraphs bothadmit an FPTRAS. These approximation schemes are based on a surprisingstructural result, which exploits ideas from Ramsey theory.

The parameterised complexity of counting even and odd induced subgraphs