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[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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bao, E., Jiang, T., Girke, T.: BRANCH: Boosting RNA-Seq assemblies with partial or related genomic sequences. Bioinformatics 29(10), 1250–1259 (2013)
Bonizzoni, P., Dondi, R., Pirola, Y.: Maximum disjoint paths on edge-colored graphs: Approximability and tractability. Algorithms 6(1), 1–11 (2013)
Downey, R., Fellows, M.: Parameterized complexity. Springer (1999)
Downey, R., Fellows, M.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141(1&2), 109–131 (1995)
Eriksson, N., Pachter, L., Mitsuya, Y., Rhee, S., Wang, C., Gharizadeh, B., Ronaghi, M., Shafer, R., Beerenwinkel, N.: Viral population estimation using pyrosequencing. PLoS Computational Biology 4(5), e1000074 (2008)
Fulkerson, D.R.: Note on Dilworth’s decomposition theorem for partially ordered sets. Proc. American Mathematical Society 7, 701–702 (1956)
Gabow, H., Maheshwari, S., Osterweil, L.: On two problems in the generation of program test paths. IEEE Trans.on Software Engineering 2(3), 227–231 (1976)
Garey, M., Johnson, D.: Computer and intractability: A guide to the theory of NP-completeness. W. H. Freeman (1979)
Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Univ. Press (2006)
Ntafos, S., Hakimi, S.: On path cover problems in digraphs and applications to program testing. IEEE Trans. on Software Engineering 5(5), 520–529 (1979)
Trapnell, C., Williams, B., Pertea, G., Mortazavi, A., Kwan, G., van Baren, M., Salzberg, S., Wold, B., Pachter, L.: Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation. Nature Biotechnology 28(5), 516–520 (2010)
Wu, B.Y.: On the maximum disjoint paths problem on edge-colored graphs. Discrete Optimization 9(1), 50–57 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y. (2014). Covering Pairs in Directed Acyclic Graphs. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)