{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:25:27Z","timestamp":1760243127469,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2015,10,9]],"date-time":"2015-10-09T00:00:00Z","timestamp":1444348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph D and an undirected graph G on the same vertex set, and the sought pattern is a path P in D whose vertex set induces a connected subgraph of G. In this context, three concrete problems arise, depending on whether the existence of P is questioned or whether the length of P is to be optimized: in that case, one can search for a longest path or (maybe less intuitively) a shortest one. These problems have immediate applications in biological networks and predictable applications in social, information and communication networks. We study the classic and parameterized complexity of the problem, thus identifying polynomial and NP-complete cases, as well as fixed-parameter tractable and W[1]-hard cases. We also propose two enumeration algorithms that we evaluate on synthetic and biological data.<\/jats:p>","DOI":"10.3390\/a8040810","type":"journal-article","created":{"date-parts":[[2015,10,9]],"date-time":"2015-10-09T11:37:33Z","timestamp":1444390653000},"page":"810-831","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Finding Supported Paths in Heterogeneous Networks"],"prefix":"10.3390","volume":"8","author":[{"given":"Guillaume","family":"Fertin","sequence":"first","affiliation":[{"name":"LINA, UMR CNRS 6241, Universit\u00e9 de Nantes, Nantes 44322, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, Technische Universit\u00e4t Berlin, Berlin D-10587, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hafedh","family":"Mohamed-Babou","sequence":"additional","affiliation":[{"name":"LINA, UMR CNRS 6241, Universit\u00e9 de Nantes, Nantes 44322, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irena","family":"Rusu","sequence":"additional","affiliation":[{"name":"LINA, UMR CNRS 6241, Universit\u00e9 de Nantes, Nantes 44322, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,10,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cai, D., Shao, Z., He, X., Yan, X., and Han, J. (2005, January 21\u201325). Mining Hidden Community in Heterogeneous Social Networks. Proceedings of the ACM-SIGKDD Workshop on Link Discovery: Issues, Approaches and Applications (LinkKDD 2005), Chicago, IL, USA.","DOI":"10.1145\/1134271.1134280"},{"key":"ref_2","unstructured":"Matsuo, Y., Hamasaki, M., Takeda, H., Mori, J., Bollegara, D., Nakamura, Y., Nishimura, T., Hasida, K., and Ishizuka, M. (2006, January 16\u201320). Spinning Multiple Social Networks for Semantic Web. Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI 2006), Boston, MA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ponce, J., and Karahoca, A. (2009). Data Mining and Knowledge Discovery in Real Life Applications, In-Tech.","DOI":"10.5772\/97"},{"key":"ref_4","unstructured":"Bunke, H. (2000, January 14\u201317). Graph matching: Theoretical foundations, algorithms and applications. Proceedings of the International Conference on Vision Interface (VI 2000), Montr\u00e9al, QC, Canada."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty years of graph matching in pattern recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"D\u017eeroski, S. (2010). Relational Data Mining, Springer.","DOI":"10.1007\/978-0-387-09823-4_46"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kelley, B.P., Yuan, B., Lewitter, F., Sharan, R., Stockwell, B.R., and Ideker, T. (2004). PathBLAST: A tool for alignment of protein interaction networks. Nucleic Acids Res., 32.","DOI":"10.1093\/nar\/gkh411"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1978","DOI":"10.1093\/bioinformatics\/btm279","article-title":"Simple and Fast Alignment of Metabolic Pathways by Exploiting Local Diversity","volume":"23","author":"Wernicke","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3401","DOI":"10.1093\/bioinformatics\/bti554","article-title":"Alignment of metabolic pathways","volume":"21","author":"Pinter","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bourqui, R., Lacroix, V., Cottret, L., Auber, D., Mary, P., Sagot, M.F., and Jourdan, F. (2007). Metabolic network visualization eliminating node redundance and preserving metabolic pathways. BMC Syst. Biol., 1.","DOI":"10.1186\/1752-0509-1-29"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1093\/bib\/bbn018","article-title":"A critical examination of stoichiometric and path-finding approaches to metabolic pathways","volume":"9","author":"Planes","year":"2008","journal-title":"Brief. Bioinform."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.jprot.2008.01.004","article-title":"Identification of dominant signaling pathways from proteomics expression data","volume":"71","author":"Zubarev","year":"2008","journal-title":"J. Proteom."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1089\/cmb.2009.0170","article-title":"Topology-Free Querying of Protein Interaction Networks","volume":"17","author":"Bruckner","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4209","DOI":"10.1093\/bioinformatics\/bti711","article-title":"Syntons, metabolons and interactons: An exact graph-theoretical approach for exploring neighbourhood between genomic and functional data","volume":"21","author":"Boyer","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Durek, P., and Walther, D. (2008). The integrated analysis of metabolic and protein interaction networks reveals novel molecular organizing principles. BMC Syst. Biol., 2.","DOI":"10.1186\/1752-0509-2-100"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1101\/gr.2131104","article-title":"Coexpression of neighboring genes in the genome of Arabidopsis thaliana","volume":"14","author":"Williams","year":"2004","journal-title":"Genome Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_19","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_21","unstructured":"Hartung, S., and Nichterlein, A. (Personal communication, 2013). Personal communication."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","article-title":"The directed subgraph homeomorphism problem","volume":"10","author":"Fortune","year":"1980","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), W. H. Freeman and Company."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","article-title":"On the parameterized complexity of multiple-interval graph problems","volume":"410","author":"Fellows","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., and Sorge, M. (2015). An Algorithmic Framework for Fixed-Cardinality Optimization in Sparse Graphs Applied to Dense Subgraph Problems. Discret. Appl. Math., in press.","DOI":"10.1016\/j.dam.2015.04.029"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic Programming Treatment of the Traveling Salesman Problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_28","unstructured":"Supported Path Software. Available online: http:\/\/fpt.akt.tu-berlin.de\/supported-path."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Cherry, J.M., Hong, E.L., Amundsen, C., Balakrishnan, R., Binkley, G., Chan, E.T., Christie, K.R., Costanzo, M.C., Dwight, S.S., and Engel, S.R. (2012). Saccharomyces Genome Database: The genomics resource of budding yeast. Nucleic Acids Res., 40.","DOI":"10.1093\/nar\/gkr1029"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"McDonald, A., Boyce, S., Moss, G., Dixon, H., and Tipton, K. (2007). ExplorEnz: A MySQL database of the IUBMB enzyme nomenclature. BMC Biochem., 8.","DOI":"10.1186\/1471-2091-8-14"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Balakrishnan, R., Park, J., Karra, K., Hitz, B.C., Binkley, G., Hong, E.L., Sullivan, J., Micklem, G., and Cherry, J.M. (2012). YeastMine\u2014An integrated data warehouse for Saccharomyces cerevisiae data as a multipurpose tool-kit. Database.","DOI":"10.1093\/database\/bar062"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Blin, G., Fertin, G., Mohamed-Babou, H., Rusu, I., Sikora, F., and Vialette, S. (2011, January 4\u20136). Algorithmic Aspects of Heterogeneous Biological Networks Comparison. Proceedings of the 5th International Conference on Combinatorial Optimization and Applications (COCOA 2011), Zhangjiajie, China.","DOI":"10.1007\/978-3-642-22616-8_22"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/810\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:49:48Z","timestamp":1760215788000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,9]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2015,12]]}},"alternative-id":["a8040810"],"URL":"https:\/\/doi.org\/10.3390\/a8040810","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2015,10,9]]}}}