GANIAN, Robert and Sebastian ORDYNIAK. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths. In Ignasi Sau and Dimitrios M. Thilikos. WG 2019: Graph-Theoretic Concepts in Computer Science. USA: Springer. p. 190-204. ISBN 978-3-030-30785-1. doi:10.1007/978-3-030-30786-8_15. 2019.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution) and Sebastian ORDYNIAK (276 Germany).
Edition USA, WG 2019: Graph-Theoretic Concepts in Computer Science, p. 190-204, 15 pp. 2019.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/19:00113728
Organization unit Faculty of Informatics
ISBN 978-3-030-30785-1
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-030-30786-8_15
UT WoS 000557920500015
Keywords in English Parameterized Complexity
Tags core_A, firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 16/5/2022 14:32.
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 treecut 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 treecut width. Our second result shows that EDP parameterized by treecut 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.
PrintDisplayed: 16/4/2024 11:41