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

DOI10.4230/LIPICS.MFCS.2019.26MaRDI QIDQ5092385FDOQ5092385

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

Publication date: 21 July 2022

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

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

zbMATH Keywords

graph homomorphismsinduced subgraphsparameterized complexitycounting complexityedge-transitive graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Paths, Trees, and Flowers
• The complexity of computing the permanent
• Parametrized complexity theory.
• Lectures on algebra. Vol. 1
• The complexity of counting homomorphisms seen from the other side
• PP is as Hard as the Polynomial-Time Hierarchy
• Strong computational lower bounds via parameterized complexity
• On recognizing graph properties from adjacency matrices
• Tight lower bounds for certain parameterized NP-hard problems
• The Parameterized Complexity of Counting Problems
• The parameterised complexity of counting even and odd induced subgraphs
• The parameterised complexity of counting connected subgraphs and graph motifs
• A topological approach to evasiveness
• Title not available (Why is that?)
• Parameterized counting problems
• Some hard families of parameterized counting problems
• Evasiveness of graph properties and topological fixed-point theorems
• Homomorphisms are a good basis for counting small subgraphs
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Title not available (Why is that?)

Cited In (1)

• Parameterized Counting and Cayley Graph Expanders

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)