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
Journal Articles Theoretical Computer Science Year : 2022

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. Positive results 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 part of size prescribed by a parameter. 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 p, where p = n − q and q is the size of the solution.
Fichier principal
Vignette du fichier
DEDP_arXiv.pdf (685.05 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03772271 , version 1 (08-09-2022)

Identifiers

Cite

Raul Lopes, Ignasi Sau. A relaxation of the Directed Disjoint Paths problem: A global congestion metric helps. Theoretical Computer Science, 2022, 898, pp.75-91. ⟨10.1016/j.tcs.2021.10.023⟩. ⟨lirmm-03772271⟩
30 View
26 Download

Altmetric

Share

More