The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113728" target="_blank" >RIV/00216224:14330/19:00113728 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/book/10.1007/978-3-030-30786-8#about" target="_blank" >https://link.springer.com/book/10.1007/978-3-030-30786-8#about</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-30786-8_15" target="_blank" >10.1007/978-3-030-30786-8_15</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

WG 2019: Graph-Theoretic Concepts in Computer Science

ISBN

9783030307851

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

190-204

Název nakladatele

Springer

Místo vydání

USA

Místo konání akce

Spanelsko

Datum konání akce

1. 1. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000557920500015