More Web Proxy on the site http://driver.im/

article

Finding and Counting Vertex-Colored Subtrees

Authors:

Sylvain Guillemot,

Florian SikoraAuthors Info & Claims

Algorithmica, Volume 65, Issue 4

Pages 828 - 844

https://doi.org/10.1007/s00453-011-9600-8

Published: 01 April 2013 Publication History

Abstract

The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4):360---368, 2006) 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 M. 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 (Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5125, pp. 575---586, 2008) and Koutis and Williams (Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5555, pp. 653---664, 2009), 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.

References

[1]

Alm, E., Arkin, A.P.: Biological networks. Curr. Opin. Struct. Biol. 13(2), 193---202 (2003)

[2]

Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42(4), 844---856 (1995)

Digital Library

[3]

Ambalath, A.M., Balasundaram, R., Rao, H.C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) Proceedings of the 5th International Symposium Parameterized and Exact Computation (IPEC). Lecture Notes in Computer Science, vol. 6478, pp. 14---25. Springer, Berlin (2010)

[4]

Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) Proceedings of the 13th International Symposium Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2518, pp. 453---464. Springer, Berlin (2002)

Digital Library

[5]

Betzler, N., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithms and hardness results for some Graph Motif problems. In: Ferragina, P., Landau, G.M. (eds.) Proceedings of the 19th Annual Symposium Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 5029, pp. 31---43. Springer, Berlin (2008)

Digital Library

[6]

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets möbius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 67---74. ACM, New York (2007)

Digital Library

[7]

Blin, G., Sikora, F., Vialette, S.: GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks. In: Al-Mubaid, H. (ed.) Proceedings of the 2nd International Conference on Bioinformatics and Computational Biology (BICoB), pp. 38---43. International Society for Computers and their Applications (ISCA), Raleigh (2010)

[8]

Böcker, S., Rasche, F., Steijger, T.: Annotating fragmentation patterns. In: Salzberg, S., Warnow, T. (eds.) Proceedings of the 9th International Workshop Algorithms in Bioinformatics (WABI). Lecture Notes in Computer Science, vol. 5724, pp. 13---24. Springer, Berlin (2009)

Digital Library

[9]

Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-free querying of Protein Interaction Networks. In: Batzoglou, S. (ed.) Proceedings of the 13th Annual International Conference Research in Computational Molecular Biology (RECOMB). Lecture Notes in Computer Science, vol. 5541, pp. 74---89. Springer, Berlin (2009)

Digital Library

[10]

Dondi, R., Fertin, G., Vialette, S.: Weak pattern matching in colored graphs: Minimizing the number of connected components. In: Italiano, G.F., Moggi, E., Laura, L. (eds.) Proceedings of the 10th Italian Conference Theoretical Computer Science (ICTCS), pp. 27---38. World Scientific, Singapore (2007)

[11]

Dondi, R., Fertin, G., Vialette, S.: Maximum motif problem in vertex-colored graphs. In: Kucherov, G., Ukkonen, E. (eds.) Proceedings of the 20th Annual Symposium Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 5577, pp. 221---235. Springer, Berlin (2009)

[12]

Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596, pp. 340---351. Springer, Berlin (2007)

Digital Library

[13]

Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892---922 (2004)

Digital Library

[14]

Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, An EATCS Series. Springer, Berlin (2006)

Digital Library

[15]

Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. In: Hlinený, P., Kucera, A. (eds.) Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10), Brno, Czech Republic. Lecture Notes in Computer Science, vol. 6281, pp. 405---416. Springer, Berlin (2010)

Digital Library

[16]

Hüffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica 52(2), 114---132 (2008)

[17]

Karp, R.: Dynamic-programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1, 49---51 (1982)

Digital Library

[18]

Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5125, pp. 575---586. Springer, Berlin (2008)

Digital Library

[19]

Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5555, pp. 653---664. Springer, Berlin (2009)

Digital Library

[20]

Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4), 360---368 (2006)

Digital Library

[21]

Nederlof, J.: Fast polynomial-space algorithms using Möbius inversion: Improving on steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Proceedings of the 36th International Colloquium Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5555, pp. 713---725. Springer, Berlin (2009)

Digital Library

[22]

Schbath, S., Lacroix, V., Sagot, M.F.: Assessing the exceptionality of coloured motifs in networks. EURASIP J. Bioinform. Syst. Biol. 2009, 1---9 (2009)

Digital Library

[23]

Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24(4), 427---433 (2006)

[24]

Williams, R.: Finding paths of length k in O*(2k) time. Inf. Process. Lett. 109(6), 315---318 (2009)

Digital Library

Cited By

Ribeiro PParedes PSilva MAparicio DSilva F(2021)A Survey on Subgraph CountingACM Computing Surveys10.1145/343365254:2(1-36)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3433652
Chandrasekaran KGrigorescu EIstrate GKulkarni SLin YZhu M(2021)The Maximum Binary Tree ProblemAlgorithmica10.1007/s00453-021-00836-583:8(2427-2468)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00453-021-00836-5
Rubert DAraujo EStefanes MStoye JMartinez F(2020)Searching and inferring colorful topological motifs in vertex-colored graphsJournal of Combinatorial Optimization10.1007/s10878-020-00590-440:2(379-411)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1007/s10878-020-00590-4
Show More Cited By

Finding and Counting Vertex-Colored Subtrees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Complexity issues in vertex-colored graph pattern matching

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In the context of metabolic network analysis, Lacroix et al. [V. Lacroix, C.G. Fernandes, M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and ...
Parameterized complexity of vertex colouring

For a family F of graphs and a nonnegative integer k, F + ke and F - ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F + kv denotes the family of graphs that can be made into ...
Parameterized complexity of vertex deletion into perfect graph classes

Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F-Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 65, Issue 4

April 2013

216 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ribeiro PParedes PSilva MAparicio DSilva F(2021)A Survey on Subgraph CountingACM Computing Surveys10.1145/343365254:2(1-36)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3433652
Chandrasekaran KGrigorescu EIstrate GKulkarni SLin YZhu M(2021)The Maximum Binary Tree ProblemAlgorithmica10.1007/s00453-021-00836-583:8(2427-2468)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00453-021-00836-5
Rubert DAraujo EStefanes MStoye JMartinez F(2020)Searching and inferring colorful topological motifs in vertex-colored graphsJournal of Combinatorial Optimization10.1007/s10878-020-00590-440:2(379-411)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1007/s10878-020-00590-4
Pinter RShachnai HZehavi M(2019)Improved Parameterized Algorithms for Network Query ProblemsAlgorithmica10.1007/s00453-018-00535-881:6(2270-2316)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-00535-8
Bergé PMouscadet BRimmel ATomasik J(2019)Fixed-Parameter Tractability of Counting Small Minimum (S, T)-CutsGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-30786-8_7(79-92)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-30786-8_7
Fomin FLokshtanov DPanolan FSaurabh S(2017)Representative Families of Product FamiliesACM Transactions on Algorithms10.1145/303924313:3(1-29)Online publication date: 13-Mar-2017
https://dl.acm.org/doi/10.1145/3039243
Chapelle MCochefert MKratsch DLetourneur RLiedloff M(2017)Exact exponential algorithms to find tropical connected sets of minimum sizeTheoretical Computer Science10.1016/j.tcs.2017.03.003676:C(33-41)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2017.03.003
Bonnet dSikora F(2017)The Graph Motif problem parameterized by the structure of the input graphDiscrete Applied Mathematics10.1016/j.dam.2016.11.016231:C(78-94)Online publication date: 20-Nov-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.11.016
Kowalik ŁLauri J(2016)On finding rainbow and colorful pathsTheoretical Computer Science10.1016/j.tcs.2016.03.017628:C(110-114)Online publication date: 16-May-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.03.017
(2016)Parameterized algorithms for the Module Motif problemInformation and Computation10.1016/j.ic.2016.08.005251:C(179-193)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.08.005
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents