Covering pairs in directed acyclic graphs

DOI10.1007/978-3-319-04921-2_10zbMATH Open1407.68203arXiv1310.5037OpenAlexW2126924325MaRDI QIDQ5404906FDOQ5404906

Authors: Niko Beerenwinkel, Stefano Beretta, Riccardo Dondi, Yuri Pirola, Paola Bonizzoni 

Publication date: 31 March 2014

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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 path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-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.

Full work available at URL: https://arxiv.org/abs/1310.5037

Recommendations

• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Sparse dynamic programming on DAGs with small width
• On the computational complexity of path cover problems
• Nontrivial path covers of graphs: existence, minimization and maximization
• Computing directed Steiner path covers for directed co-graphs (extended abstract)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (9)

• On the Sound Covering Cycle Problem in Paired de Bruijn Graphs
• Minimum interval cover and its application to genome sequencing
• An external-memory algorithm for string graph construction
• Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers
• On the computational complexity of path cover problems
• Sparse dynamic programming on DAGs with small width
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• Acyclic graphoidal covers and path partitions in a graph

This page was built for publication: Covering pairs in directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404906)