Ganian, Robert ;
Ordyniak, Sebastian ;
Sridharan, Ramanujan
On Structural Parameterizations of the Edge Disjoint Paths Problem
Abstract
In this paper we revisit 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 edgedisjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomialtime or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixedparameter tractable.
Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NPhard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in nonuniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an fptalgorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fptalgorithm for EDP by exploiting a novel structural parameter of the augmented graph.
BibTeX  Entry
@InProceedings{ganian_et_al:LIPIcs:2017:8255,
author = {Robert Ganian and Sebastian Ordyniak and Ramanujan Sridharan},
title = {{On Structural Parameterizations of the Edge Disjoint Paths Problem}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {36:136:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8255},
URN = {urn:nbn:de:0030drops82555},
doi = {10.4230/LIPIcs.ISAAC.2017.36},
annote = {Keywords: edge disjoint path problem, feedback vertex set, treewidth, fracture number, parameterized complexity}
}
2017
Keywords: 

edge disjoint path problem, feedback vertex set, treewidth, fracture number, parameterized complexity 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

2017 