Counting induced subgraphs: an algebraic approach to \#W[1]-hardness

DOI10.4230/LIPICS.MFCS.2019.26MaRDI QIDQ5092385zbMATH OpenFDO

Authors Julian Dörfler, Marc Roth, Johannes Schmitt, Philip Wellnitz

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1904.10479

zbMATH Keywords

counting complexityedge-transitive graphsgraph homomorphismsinduced subgraphsparameterized complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Some hard families of parameterized counting problems
• The parameterised complexity of counting even and odd induced subgraphs

Cites work

• A topological approach to evasiveness
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Evasiveness of graph properties and topological fixed-point theorems
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 2165490 (Why is no real title available?)
• Large networks and graph limits
• Lectures on algebra. Vol. 1
• On recognizing graph properties from adjacency matrices
• Parameterized counting problems
• Parametrized complexity theory.
• Paths, Trees, and Flowers
• PP is as Hard as the Polynomial-Time Hierarchy
• Some hard families of parameterized counting problems
• Strong computational lower bounds via parameterized complexity
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• The parameterised complexity of counting connected subgraphs and graph motifs
• The parameterised complexity of counting even and odd induced subgraphs
• The Parameterized Complexity of Counting Problems
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(9)

• The parameterised complexity of counting even and odd induced subgraphs
• Some hard families of parameterized counting problems
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Parameterized Counting and Cayley Graph Expanders
• Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness

This page was built for publication: Counting induced subgraphs: an algebraic approach to \#W[1]-hardness

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