The parameterised complexity of counting connected subgraphs and graph motifs
From MaRDI portal
Publication:2256721
DOI10.1016/j.jcss.2014.11.015zbMath1320.68101arXiv1308.1575OpenAlexW2962738766MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (17)
Compactors for parameterized counting problems ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ 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 ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ On Counting Parameterized Matching and Packing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Some Hard Families of Parameterized Counting Problems ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness]
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]
This page was built for publication: The parameterised complexity of counting connected subgraphs and graph motifs
