The parameterised complexity of counting even and odd induced subgraphs

DOI10.1007/S00493-016-3338-5MaRDI QIDQ1714949zbMATH OpenOpenAlexWikidataFDO

Authors Kitty Meeks, Mark Jerrum

Publication date 1 February 2019

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3375, http://eprints.gla.ac.uk/111146/7/111146.pdf

zbMATH Keywords

counting induced subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30)

Abstract: 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 the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that the problems of counting even and odd k-vertex induced subgraphs both admit an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory.

Recommendations

• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness

Cited in

(18)

• Parameterized complexity of connected even/odd subgraph problems
• Compactors for parameterized counting problems
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Some hard families of parameterized counting problems
• Counting Small Induced Subgraphs with Hereditary Properties
• Parameterised counting in logspace
• Counting problems in parameterized complexity
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• The parameterized complexity of k-edge induced subgraphs
• The Parameterized Complexity of k-Edge Induced Subgraphs
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• On the complexity of finding large odd induced subgraphs and odd colorings
• Parameterized Counting and Cayley Graph Expanders

This page was built for publication: The parameterised complexity of counting even and odd induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1714949)