Skip to Main content Skip to Navigation
Conference papers

On the complexity of finding internally vertex-disjoint long directed paths

Abstract : For two positive integers k and , a (k ×)-spindle is the union of k pairwise internally vertex-disjoint directed paths with arcs between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed ≥ 1, finding the largest k such that an input digraph G contains a subdivision of a (k ×)-spindle is polynomial-time solvable if ≤ 3, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.
Document type :
Conference papers
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410722
Contributor : Ignasi Sau <>
Submitted on : Friday, December 13, 2019 - 11:28:24 PM
Last modification on : Wednesday, June 24, 2020 - 10:48:04 AM

File

1706.09066.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Julio Araujo, Victor Campos, Ana Karolinna Maia, Ignasi Sau Valls, Ana Silva. On the complexity of finding internally vertex-disjoint long directed paths. 13th Latin American Symposium on Theoretical Informatics (LATIN), Apr 2018, Buenos Aires, Argentina. pp.66-79, ⟨10.1007/978-3-319-77404-6_6⟩. ⟨lirmm-02410722⟩

Share

Metrics

Record views

168

Files downloads

446