Skip to Main content Skip to Navigation
Conference papers

A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Raul Lopes 1, 2 Ignasi Sau Valls 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s1, t1),. .. , (s k , t k)}, and the task is to find a collection of pairwise vertex-disjoint paths {P1,. .. , P k } such that each Pi is a path from si to ti in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time O(n d+2 · k d·s) and a kernel of size d · 2 k−s · k s + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n − c and c is the size of the solution.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02991855
Contributor : Isabelle Gouat <>
Submitted on : Friday, November 6, 2020 - 10:45:03 AM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Sunday, February 7, 2021 - 6:32:30 PM

File

LIPIcs-MFCS-2020-68.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Raul Lopes, Ignasi Sau Valls. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.68:1-68:15, ⟨10.4230/LIPIcs.MFCS.2020.68⟩. ⟨lirmm-02991855⟩

Share

Metrics

Record views

33

Files downloads

15