Counting induced subgraphs: a topological approach to \#W[1]-hardness
DOI10.1007/S00453-020-00676-9zbMATH Open1452.68086OpenAlexW2963918649WikidataQ98500017 ScholiaQ98500017MaRDI QIDQ786040FDOQ786040
Authors: Marc Roth, Johannes Schmitt 
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
Recommendations
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- The parameterised complexity of counting connected subgraphs and graph motifs
- Some hard families of parameterized counting problems
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30) Combinatorial aspects of simplicial complexes (05E45) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- The on-line encyclopedia of integer sequences
- Large networks and graph limits
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Title not available (Why is that?)
- The complexity of computing the permanent
- Simplicial complexes of graphs
- Parametrized complexity theory.
- On the Structure of Polynomial Time Reducibility
- The complexity of counting homomorphisms seen from the other side
- Strong computational lower bounds via parameterized complexity
- On recognizing graph properties from adjacency matrices
- Fixed-point sets of group actions on finite acyclic complexes
- Tight lower bounds for certain parameterized NP-hard problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- 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
- Evasiveness of subgraph containment and related properties
- Some results related to the evasiveness conjecture.
- Title not available (Why is that?)
- Some hard families of parameterized counting problems
- Evasiveness of graph properties and topological fixed-point theorems
- Title not available (Why is that?)
- Homomorphisms are a good basis for counting small subgraphs
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- The challenges of unbounded treewidth in parameterised subgraph counting problems
Cited In (10)
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
- Counting Small Induced Subgraphs with Hereditary Properties
- Counting problems in parameterized complexity
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Parameterized counting of partially injective homomorphisms
- The parameterised complexity of counting connected subgraphs and graph motifs
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Parameterized Counting and Cayley Graph Expanders
Uses Software
This page was built for publication: Counting induced subgraphs: a topological approach to \#W[1]-hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786040)
