Abstract
We study the classic Graph Motif problem: given a graph G = (V,E) with a set of colors for each node, and a multiset M of colors, we seek a subtree T ⊆ G, and a coloring of the nodes in T, such that T carries exactly (also with respect to multiplicity) the colors in M. Graph Motif plays a central role in the study of pattern matching problems, primarily motivated from the analysis of complex biological networks.
Previous algorithms for Graph Motif and its variants either rely on techniques for developing randomized algorithms that, if derandomized, render them inefficient, or the algebraic narrow sieves technique for which there is no known derandomization. In this paper, we present fast deterministic parameterized algorithms for Graph Motif and its variants. Specifically, we give such an algorithm for the more general Graph Motif with Deletions problem, followed by faster algorithms for Graph Motif and other well-studied special cases. Our algorithms make non-trivial use of representative families, and a novel tool that we call guiding trees, together enabling the efficient construction of the output tree.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color coding. J. Assoc. Comput. Mach. 42(4), 844–856 (1995)
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.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010)
Betzler, N., Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 8(5), 1296–1308 (2011)
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.) CPM 2008. LNCS, vol. 5029, pp. 31–43. Springer, Heidelberg (2008)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. CoRR abs/1007.1161 (2010)
Björklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: STACS, pp. 20–31 (2013)
Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-free querying of protein interaction networks. J. Comput. Biol. 17(3), 237–252 (2010)
Dondi, R., Fertin, G., Vialette, S.: Finding approximate and constrained motifs in graphs. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 388–401. Springer, Heidelberg (2011)
Dondi, R., Fertin, G., Vialette, S.: Maximum motif problem in vertex-colored graphs. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol. 5577, pp. 221–235. Springer, Heidelberg (2009)
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., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340–351. Springer, Heidelberg (2007)
Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799–811 (2011)
Fionda, V., Palopoli, L.: Biological network querying techniques: Analysis and comparison. J. Comput. Biol. 18(4), 595–625 (2011)
Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact agorithms. In: SODA (see also: CoRR abs/1304.4626), pp. 142–151 (2014)
Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 405–416. Springer, Heidelberg (2010)
Koutis, I.: Constrained multilinear detection for faster functional motif discovery. Inf. Process. Lett. 112(22), 889–892 (2012)
Koyutürk, M.: Algorithmic and analytical methods in network biology. Wiley Interdiscip. Rev. Syst. Biol. Med. 2(3), 277–292 (2010)
Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: Application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 360–368 (2006)
Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. CoRR abs/1404.4506 (2014)
Oxley, J.G.: Matroid theory. Oxford University Press (2006)
Pinter, R.Y., Shachnai, S., Zehavi, M.: Deterministic parameterized algorithms for the graph motif problem, http://www.cs.technion.ac.il/~hadas/PUB/Graph_Motif_full.pdf
Pinter, R.Y., Zehavi, M.: Partial information network queries. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 362–375. Springer, Heidelberg (2013)
Pinter, R.Y., Zehavi, M.: Algorithms for topology-free and alignment network queries. J. Discrete Algorithms (to appear, 2014)
Pinter-Wollman, N., Hobson, E.A., Smith, J.E., Edelman, A.J., Shizuka, D., de Silva, S., Waters, J.S., Prager, S.D., Sasaki, T., Wittemyer, G., Fewell, J., McDonald, D.B.: The dynamics of animal social networks: analytical, conceptual, and theoretical advances. Behavioral Ecology 25(2), 242–255 (2014)
Rizzi, R., Sikora, F.: Some results on more flexible versions of graph motif. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 278–289. Springer, Heidelberg (2012)
Shachnai, H., Zehavi, M.: Faster computation of representative families for uniform matroids with applications. CoRR abs/1402.3547 (2014)
Sikora, F.: An (almost complete) state of the art around the graph motif problem. Université Paris-Est Technical reports (2012)
Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: STOC, pp. 887–898 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pinter, R.Y., Shachnai, H., Zehavi, M. (2014). Deterministic Parameterized Algorithms for the Graph Motif Problem. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_50
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)