The parameterised complexity of counting connected subgraphs and graph motifs

DOI10.1016/j.jcss.2014.11.015zbMath1320.68101arXiv1308.1575MaRDI QIDQ2256721

Kitty Meeks, Mark R. Jerrum

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

zbMATH Keywords

counting complexity; parameterised complexity; FPTRAS

Mathematics Subject Classification ID

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]