Counting induced subgraphs: a topological approach to \#W[1]-hardness
From MaRDI portal
Publication:786040
Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of simplicial complexes (05E45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
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
Cites work
- A topological approach to evasiveness
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Evasiveness of graph properties and topological fixed-point theorems
- Evasiveness of subgraph containment and related properties
- Fixed-point sets of group actions on finite acyclic complexes
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- scientific article; zbMATH DE number 7075922 (Why is no real title available?)
- scientific article; zbMATH DE number 3390006 (Why is no real title available?)
- Large networks and graph limits
- On recognizing graph properties from adjacency matrices
- On the Structure of Polynomial Time Reducibility
- Parametrized complexity theory.
- Simplicial complexes of graphs
- Some hard families of parameterized counting problems
- Some results related to the evasiveness conjecture.
- 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 complexity of homomorphism and constraint satisfaction problems seen from the other side
- The on-line encyclopedia of integer sequences
- 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
- Tight lower bounds for certain parameterized NP-hard problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
Cited in
(15)- Parameterized counting of partially injective homomorphisms
- The parameterised complexity of counting connected subgraphs and graph motifs
- 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
- Counting problems in parameterized complexity
- 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
- Counting Small Induced Subgraphs with Hereditary Properties
- Parameterized Counting and Cayley Graph Expanders
- Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
- Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
- Can you link up with treewidth?
- Counting small induced subgraphs: scorpions are easy but not trivial
- Can you link up with treewidth?
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
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)
