A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2020

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

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.
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2020-68.pdf (621.34 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-02991855 , version 1 (06-11-2020)

Licence

Identifiers

Cite

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

Altmetric

Share

More