Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness
type: Item
instance of: scholarly article
title: Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness
author: Julian Dörfler
author: Marc Roth
author: Johannes Schmitt
author: Philip Wellnitz
published in: Algorithmica
publication date: 2022-03-25T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7498364
zbMATH Keywords: counting complexity
zbMATH Keywords: edge-transitive graphs
zbMATH Keywords: graph homomorphisms
zbMATH Keywords: induced subgraphs
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
full work available at URL: s00453-021-00894-9
OpenAlex ID: W2941191312
cites work: Q5486492
cites work: Algebraic Graph Theory
cites work: The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Strong computational lower bounds via parameterized complexity
cites work: Q4967222
cites work: Homomorphisms are a good basis for counting small subgraphs
cites work: The complexity of counting homomorphisms seen from the other side
cites work: Paths, Trees, and Flowers
cites work: The Parameterized Complexity of Counting Problems
cites work: Parametrized complexity theory.
cites work: The parameterised complexity of counting connected subgraphs and graph motifs
cites work: Some hard families of parameterized counting problems
cites work: The parameterised complexity of counting even and odd induced subgraphs
cites work: A topological approach to evasiveness
cites work: Q4899293
cites work: Parameterized counting problems
cites work: The challenges of unbounded treewidth in parameterised subgraph counting problems
cites work: Evasiveness of graph properties and topological fixed-point theorems
cites work: On recognizing graph properties from adjacency matrices
cites work: Q5009487
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: The complexity of computing the permanent
cites work: The Sylow Subgroups of the Symmetric Groups
cites work: Finding Four-Node Subgraphs in Triangle Time
DOI: 10.1007/S00453-021-00894-9
description: scientific article; zbMATH DE number 7498364