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[1]-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

BERETTA, STEFANO;BONIZZONI, PAOLA;PIROLA, YURI
2015

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[1]-hard when parameterized by the number of covered pairs and we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree.
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 Dimensione Formato  
journ-art-15-compj.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 344.06 kB
Formato Adobe PDF
344.06 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/84537
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
Social impact