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

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

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

(24)

• The parameterised complexity of counting connected subgraphs and graph motifs
• Some hard families of parameterized counting problems
• The Parameterized Complexity of k-Edge Induced Subgraphs
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of connected even/odd subgraph problems
• Counting problems in parameterized complexity
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• On the complexity of finding large odd induced subgraphs and odd colorings
• Parameterised counting in logspace
• Counting Small Induced Subgraphs with Hereditary Properties
• Parameterized Counting and Cayley Graph Expanders
• Parameterized complexity of even/odd subgraph problems
• Parameterised counting in logspace
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Improved algorithms for perfect graphs and odd holes
• Can you link up with treewidth?
• The parameterized complexity of k-edge induced subgraphs
• Which graph motif parameters count?
• Can you link up with treewidth?
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Compactors for parameterized counting problems
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness

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)