The parameterised complexity of counting even and odd induced subgraphs

Mark Jerrum, Kitty Meeks

We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting t…