Abstract
In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s₁, t₁), …, (s_k, t_k)}, and the task is to find a collection of pairwise vertexdisjoint paths {P₁, …, P_k} such that each P_i is a path from s_i to t_i in D. This problem is NPcomplete 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 treewidth, 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 nvertex digraph D, a set of k requests, and nonnegative 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 treewidth 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 𝒪(n^{d+2} ⋅ k^{d⋅ s}) and a kernel of size d ⋅ 2^{ks}⋅ binom(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.
BibTeX  Entry
@InProceedings{lopes_et_al:LIPIcs:2020:12737,
author = {Raul Lopes and Ignasi Sau},
title = {{A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {68:168:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12737},
URN = {urn:nbn:de:0030drops127378},
doi = {10.4230/LIPIcs.MFCS.2020.68},
annote = {Keywords: Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed treewidth}
}
Keywords: 

Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed treewidth 
Collection: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 
Issue Date: 

2020 
Date of publication: 

18.08.2020 