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

DOI10.1007/s00453-021-00894-9OpenAlexW2941191312MaRDI QIDQ832520

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

Publication date: 25 March 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphsgraph homomorphismsparameterized complexitycounting complexityedge-transitive graphs

Mathematics Subject Classification ID

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

Related Items (4)

Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Counting Small Induced Subgraphs with Hereditary Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• Strong computational lower bounds via parameterized complexity
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• A topological approach to evasiveness
• On recognizing graph properties from adjacency matrices
• The parameterised complexity of counting even and odd induced subgraphs
• The parameterised complexity of counting connected subgraphs and graph motifs
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Parameterized counting problems
• Some Hard Families of Parameterized Counting Problems
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems
• PP is as Hard as the Polynomial-Time Hierarchy
• The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
• Algebraic Graph Theory
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Paths, Trees, and Flowers
• Finding Four-Node Subgraphs in Triangle Time
• The Sylow Subgroups of the Symmetric Groups

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