Finding supported paths in heterogeneous networks
type: Item
instance of: scholarly article
title: Finding supported paths in heterogeneous networks
zbMATH Open document ID: 1461.68151
author: Guillaume Fertin
author: Christian Komusiewicz
author: Hafedh Mohamed-Babou
author: Irena Rusu
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 92C42
zbMATH DE Number: 7042287
zbMATH Keywords: NP-hard problems
zbMATH Keywords: directed acyclic graphs
zbMATH Keywords: longest path problem
zbMATH Keywords: shortest path problem
zbMATH Keywords: protein interaction networks
zbMATH Keywords: metabolic networks
describes a project that uses: PathBLAST
describes a project that uses: MySQL
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a8040810
OpenAlex ID: W1885685411
cites work: Parametrized complexity theory.
cites work: Q5710169
cites work: The directed subgraph homeomorphism problem
cites work: Q4198056
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
cites work: Dynamic Programming Treatment of the Travelling Salesman Problem
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Algorithmic Aspects of Heterogeneous Biological Networks Comparison
DOI: 10.3390/A8040810
description: scientific article; zbMATH DE number 7042287