Skip to main content
Springer Nature Link
Log in

Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

  • Conference paper
Automata, Languages and Programming (ICALP 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4596))

Included in the following conference series:

  • 1557 Accesses

Abstract

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem has applications in metabolic network analysis, an important area in bioinformatics. We give two positive results and three negative results that together draw sharp borderlines between tractable and intractable instances of the problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Robertson, N., Seymoued, P. (eds.), Graph Structure Theory, pp. 539–564 (1993)

    Google Scholar 

  2. Alon, N., Yuster, R., Zwick, U.: Color coding. Journal of the ACM 42(4), 844–856 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  3. Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey. BIT Numerical Mathematics 25(1), 2–23 (1985)

    MATH  MathSciNet  Google Scholar 

  4. Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics 23, 11–24 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1–23 (1993)

    MATH  MathSciNet  Google Scholar 

  6. Bodlaender, H.L., Fluiter, L.E.: Intervalizing k-colored graphs. In: Fülöp, Z., Gecseg, F. (eds.) Automata, Languages and Programming. LNCS, vol. 944, pp. 87–98. Springer, Heidelberg (1995)

    Google Scholar 

  7. Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Kernelization for convex recoloring. In: Proceedings of the 2nd workshop on Algorithms and Complexity in Durham (ACiD), pp. 23–35 (2006)

    Google Scholar 

  8. Bodlaender, H.L., Fellows, M.R., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) Automata, Languages and Programming. LNCS, vol. 623, pp. 273–283. Springer, Heidelberg (1992)

    Google Scholar 

  9. Chor, B., Fellows, M.R., Ragan, M.A., Rosamond, F.A., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity – Manuscript (2007)

    Google Scholar 

  10. Corneil, D.G., Keil, J.M.: A dynamic programming approach to the dominating set problem on k-trees. SIAM Journal on Algebraic and Discrete Methods 8(4), 535–543 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  11. Deville, Y., Gilbert, D., Helden, J.V., Wodak, S.J.: An overview of data models for the analysis of biochemical pathways. Briefings in Bioinformatics 4(3), 246–259 (2003)

    Article  Google Scholar 

  12. Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)

    Google Scholar 

  13. Fellows, M.R., Hallett, M.T., Wareham, H.T.: DNA physical mapping: Three ways difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 157–168. Springer, Heidelberg (1993)

    Google Scholar 

  14. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    MATH  Google Scholar 

  15. Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Advances in Applied Mathematics 15, 251–261 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  16. Ideker, T., Karp, R.M., Scott, J., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. Journal of Computational Biology 13(2), 133–144 (2006)

    Article  MathSciNet  Google Scholar 

  17. Kelley, B.P., Sharan, R., Karp, R.M., Sittler, T., Root, D.E., Stockwell, B.R., Ideker, T.: Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proceedings of the National Academy of Sciences of the United States of America 100(20), 11394–11399 (2003)

    Article  Google Scholar 

  18. Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: Application to metabolic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4), 360–368 (2006)

    Article  Google Scholar 

  19. McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulating vertex-colored graphs. SIAM Journal on Discrete Mathematics 7(2), 296–306 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  20. Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 218–232. Springer, Heidelberg (2005)

    Google Scholar 

  21. Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. In: STOC. Proceedings of the 25th annual ACM Symposium on Theory Of Computing, pp. 213–223. ACM Press, New York (1990)

    Google Scholar 

  22. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. SIAM Journal of Algorithms 7, 309–322 (1986)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The University of Newcastle, Callaghan NSW 2308, Australia

    Michael R. Fellows

  2. Institute of Advanced Study, Durham University, Durham DH1 3RL, United Kingdom

    Michael R. Fellows

  3. Laboratoire d’Informatique de Nantes-Atlantique (LINA), FRE CNRS 2729, Université de Nantes, 2 rue de la Houssinière, 44322 Nantes Cedex 3, France

    Guillaume Fertin

  4. Department of Computer Science, University of Haifa, Mount Carmel, Haifa 31905, Israel

    Danny Hermelin

  5. Laboratoire de Recherche en Informatique (LRI), UMR CNRS 8623, Faculté des Sciences d’Orsay - Université Paris-Sud, 91405 Orsay, France

    Stéphane Vialette

Authors
  1. Michael R. Fellows
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guillaume Fertin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Danny Hermelin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stéphane Vialette
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Lars Arge Christian Cachin Tomasz Jurdziński Andrzej Tarlecki

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S. (2007). Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73420-8_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73420-8_31

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73419-2

  • Online ISBN: 978-3-540-73420-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation