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

DOI10.1007/S00453-021-00894-9MaRDI QIDQ832520zbMATH OpenOpenAlexFDO

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

Publication date 25 March 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-021-00894-9

zbMATH Keywords

counting complexityedge-transitive graphsgraph homomorphismsinduced subgraphsparameterized complexity

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

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
• Algebraic Graph Theory
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Evasiveness of graph properties and topological fixed-point theorems
• Finding four-node subgraphs in triangle time
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 7075922 (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
• The parity of set systems under random restrictions with applications to exponential time problems
• The Sylow Subgroups of the Symmetric Groups
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(16)

• The parameterised complexity of counting even and odd induced subgraphs
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• The parameterised complexity of counting connected subgraphs and graph motifs
• Some hard families of parameterized counting problems
• 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
• Parameterised and fine-grained subgraph counting, modulo 2
• Counting Small Induced Subgraphs with Hereditary Properties
• Counting subgraphs in somewhere dense graphs
• Finding and counting patterns in sparse graphs
• Can you link up with treewidth?
• Which graph motif parameters count?
• Counting small induced subgraphs: scorpions are easy but not trivial
• Can you link up with treewidth?
• Counting induced subgraphs: a topological 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 Q832520)