Finding and counting vertex-colored subtrees
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)
Abstract: The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors . It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis et al., we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.
Recommendations
- Finding and counting vertex-colored subtrees
- The graph motif problem parameterized by the structure of the input graph
- Maximum Motif Problem in Vertex-Colored Graphs
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Complexity issues in vertex-colored graph pattern matching
Cites work
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Color-coding
- Dynamic programming meets the principle of inclusion and exclusion
- Finding and counting vertex-colored subtrees
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Fourier meets M\"{o}bius: fast subset convolution
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- Maximum Motif Problem in Vertex-Colored Graphs
- On the Kernelization Complexity of Colorful Motifs
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- The Parameterized Complexity of Counting Problems
Cited in
(31)- Partial information network queries
- The maximum binary tree problem
- Algorithms for topology-free and alignment network queries
- The parameterised complexity of counting connected subgraphs and graph motifs
- Some results on more flexible versions of Graph Motif
- The graph motif problem parameterized by the structure of the input graph
- Improved parameterized algorithms for network query problems
- Fixed-parameter algorithms for scaffold filling
- On finding rainbow and colorful paths
- Some results on more flexible versions of Graph Motif
- Deterministic parameterized algorithms for the graph motif problem
- Exact exponential algorithms to find a tropical connected set of minimum size
- Improved parameterized algorithms for network query problems
- Deterministic parameterized algorithms for the graph motif problem
- Parameterized algorithms for the module motif problem
- Finding and counting vertex-colored subtrees
- Maximum Motif Problem in Vertex-Colored Graphs
- Finding approximate and constrained motifs in graphs
- Quasipolynomial representation of transversal matroids with applications in parameterized complexity
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Engineering motif search for large motifs
- Exact exponential algorithms to find tropical connected sets of minimum size
- Complexity issues in vertex-colored graph pattern matching
- The graph motif problem parameterized by the structure of the input graph
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- On the complexity of problems on graphs defined on groups
- Exact counting of subtrees with diameter no more than d in trees: a generating function approach
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Searching and inferring colorful topological motifs in vertex-colored graphs
- The challenges of unbounded treewidth in parameterised subgraph counting problems
This page was built for publication: Finding and counting vertex-colored subtrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1949738)
