Counting induced subgraphs: a topological approach to \#W[1]-hardness

DOI10.1007/s00453-020-00676-9zbMath1452.68086OpenAlexW2963918649WikidataQ98500017 ScholiaQ98500017MaRDI QIDQ786040

Johannes Schmitt, Marc Roth

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00676-9

zbMATH Keywords

Euler characteristicsimplicial complexeshomomorphismsparameterized complexitycounting complexity

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of simplicial complexes (05E45) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Counting Small Induced Subgraphs Satisfying Monotone Properties, Counting Small Induced Subgraphs with Hereditary Properties, Parameterized Counting and Cayley Graph Expanders, Unnamed Item, Parameterized counting of partially injective homomorphisms

Uses Software

• OEIS

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
• Fixed-point sets of group actions on finite acyclic complexes
• On recognizing graph properties from adjacency matrices
• The parameterised complexity of counting even and odd induced subgraphs
• Some results related to the evasiveness conjecture.
• The parameterised complexity of counting connected subgraphs and graph motifs
• Simplicial complexes of graphs
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Evasiveness of Subgraph Containment and Related Properties
• Some Hard Families of Parameterized Counting Problems
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems
• Understanding the Complexity of Induced Subgraph Isomorphisms
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On the Structure of Polynomial Time Reducibility
• The on-line encyclopedia of integer sequences
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices