The parameterised complexity of counting connected subgraphs and graph motifs
From MaRDI portal
Publication:2256721
DOI10.1016/j.jcss.2014.11.015zbMath1320.68101arXiv1308.1575MaRDI QIDQ2256721
Publication date: 20 February 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1308.1575
68Q25: Analysis of algorithms and problem complexity
05C30: Enumeration in graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
On Counting Parameterized Matching and Packing, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Counting Small Induced Subgraphs Satisfying Monotone Properties, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Counting Small Induced Subgraphs with Hereditary Properties, Parameterized Counting and Cayley Graph Expanders, Counting induced subgraphs: a topological approach to \#W[1-hardness], Compactors for parameterized counting problems, Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness], The challenges of unbounded treewidth in parameterised subgraph counting problems, Randomised enumeration of small witnesses using a decision oracle, Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, Parameterized counting matching and packing: a family of hard problems that admit FPTRAS, Some Hard Families of Parameterized Counting Problems
Cites Work
- Unnamed Item
- The complexity of counting homomorphisms seen from the other side
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- On the parameterized complexity of multiple-interval graph problems
- Parameterized complexity of finding subgraphs with hereditary properties.
- Finding and counting vertex-colored subtrees
- Parametrized complexity theory.
- On meet matrices on posets
- Parameterized counting problems
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Maximum Motif Problem in Vertex-Colored Graphs
- Color-coding
- The Parameterized Complexity of Counting Problems
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]