GANIAN, Robert, Sebastian ORDYNIAK and M.S. RAMANUJAN. On Structural Parameterizations of the Edge Disjoint Paths Problem. Online. In Yoshio Okamoto; Takeshi Tokuyama. 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand. 92nd ed. Nemecko: LIPIcs, 2017, p. 1-13. ISBN 978-3-95977-054-5. Available from: https://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.36.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name On Structural Parameterizations of the Edge Disjoint Paths Problem
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Sebastian ORDYNIAK (40 Austria) and M.S. RAMANUJAN (356 India).
Edition 92. vyd. Nemecko, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, p. 1-13, 13 pp. 2017.
Publisher LIPIcs
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10200 1.2 Computer and information sciences
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/17:00100549
Organization unit Faculty of Informatics
ISBN 978-3-95977-054-5
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.36
Keywords in English Edge Disjont Paths; Parameterized Complexity; Treewidth
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 17/5/2018 17:24.
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 edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time 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 fixed-parameter 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 NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an fpt-algorithm 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 fpt-algorithm for EDP by exploiting a novel structural parameter of the augmented graph.
PrintDisplayed: 26/8/2024 22:08