The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths
- PDF / 1,885,067 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 165 Views
The Power of Cut‑Based Parameters for Computing Edge‑Disjoint Paths Robert Ganian1 · Sebastian Ordyniak2 Received: 7 May 2019 / Accepted: 17 September 2020 © The Author(s) 2020
Abstract This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter tree-cut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded tree-cut width. Our second result shows that EDP parameterized by tree-cut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. Keywords Edge-disjoint path problem · Feedback edge set · Tree-cut width · Parameterized complexity
* Robert Ganian [email protected] Sebastian Ordyniak [email protected] 1
Algorithms and Complexity Group, Vienna University of Technology, Vienna, Austria
2
Algorithms Group, University of Sheffield, Sheffield, UK
13
Vol.:(0123456789)
Algorithmica
1 Introduction Edge-Disjoint Paths (EDP) is a fundamental routing graph problem: we are given a graph G and a set P containing pairs of vertices (terminals), and are asked to decide whether there is a set of |P| pairwise edge-disjoint paths in G connecting each pair in P. Similarly to its counterpart, the Vertex-Disjoint Paths (VDP) problem, EDP has been at the center of numerous results in structural graph theory, approximation algorithms, and parameterized algorithms [2, 8, 9, 14, 17, 19, 21, 22, 26]. Both EDP and VDP are NP-complete in general [16], and a significant amount of research has focused on identifying structural properties which make these problems tractable. For instance, Robertson and Seymour’s seminal work in the Graph Minors project [22] provides an O(n3 ) time algorithm for both problems for every fixed value of |P|. Such results are often viewed through the more refined lens of the parameterized complexity paradigm [5, 7]; there, each problem is associated with a numerical parameter k (capturing some structural property of the instance), and the goal is to obtain algorithms which are efficient when the parameter is small. Ideally, the aim is then to obtain so-called fixed-parameter algorithms for the problem, i.e., algorithms which run in time f (k) ⋅ nO(1) where f is a computable function a
Data Loading...
