The Minimum Path Cover (MinPC) problem on directed acyclic graphs (DAGs) is a classical problem in graph theory that provides a clear and simple mathematical formulation for several applications in computational biology. In this paper, we study the computational complexity of three constrained variants of MinPC motivated by the recent introduction of Next-Generation Sequencing technologies. The first variant (MinRPC), given a DAG and a set of pairs of vertices, asks for a minimum-cardinality set of (not necessarily disjoint) paths such that both vertices of each pair belong to the same path. For this problem, we establish a sharp tractability borderline depending on the 'overlapping degree' of the instance, a natural parameter in some applications of the problem. The second variant we consider (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum-cardinality set of (not necessarily disjoint) paths 'covering' all the vertices of the graph and such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The third variant (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a single path containing the maximum number of the given pairs of vertices. We show that MaxRPSP is W-hard when parameterized by the number of covered pairs and we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree.

Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y. (2015). Covering Pairs in Directed Acyclic Graphs. COMPUTER JOURNAL, 58(7), 1673-1686 [10.1093/comjnl/bxu116].

### Covering Pairs in Directed Acyclic Graphs

#### Abstract

The Minimum Path Cover (MinPC) problem on directed acyclic graphs (DAGs) is a classical problem in graph theory that provides a clear and simple mathematical formulation for several applications in computational biology. In this paper, we study the computational complexity of three constrained variants of MinPC motivated by the recent introduction of Next-Generation Sequencing technologies. The first variant (MinRPC), given a DAG and a set of pairs of vertices, asks for a minimum-cardinality set of (not necessarily disjoint) paths such that both vertices of each pair belong to the same path. For this problem, we establish a sharp tractability borderline depending on the 'overlapping degree' of the instance, a natural parameter in some applications of the problem. The second variant we consider (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum-cardinality set of (not necessarily disjoint) paths 'covering' all the vertices of the graph and such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The third variant (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a single path containing the maximum number of the given pairs of vertices. We show that MaxRPSP is W-hard when parameterized by the number of covered pairs and we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree.
##### Scheda breve Scheda completa Scheda completa (DC) Articolo in rivista - Articolo scientifico
computational complexity; minimum path cover; paired-end reads; sequence reconstruction;
minimum path cover; sequence reconstruction; paired-end reads; computational complexity
English
2015
58
7
1673
1686
reserved
Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y. (2015). Covering Pairs in Directed Acyclic Graphs. COMPUTER JOURNAL, 58(7), 1673-1686 [10.1093/comjnl/bxu116].
File in questo prodotto:
File
journ-art-15-compj.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 344.06 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/84537`
• 6
• 5