The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths “covering” all the vertices 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 second problem (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 its NP-hardness and also its W-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.

Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y. (2014). Covering Pairs in Directed Acyclic Graphs. In Language and Automata Theory and Applications (pp.126-137). Springer International Publishing [10.1007/978-3-319-04921-2_10].

### Covering Pairs in Directed Acyclic Graphs

#### Abstract

The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths “covering” all the vertices 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 second problem (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 its NP-hardness and also its W-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
##### Scheda breve Scheda completa Scheda completa (DC) slide + paper
path cover;DAG;constraints;computational complexity;bioinformatics;software testing
English
Language and Automata Theory and Applications
2014
Dediu, A-H; Martín-Vide, C; Sierra-Rodríguez, J-L; Truthe, B
Language and Automata Theory and Applications
978-3-319-04920-5
2014
8370
126
137
reserved
Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y. (2014). Covering Pairs in Directed Acyclic Graphs. In Language and Automata Theory and Applications (pp.126-137). Springer International Publishing [10.1007/978-3-319-04921-2_10].
File in questo prodotto:
File
conf-paper-14-lata.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 258.67 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/51334`
• 3
• 2