Edwards, Katherine ;
Muzi, Irene ;
Wollan, Paul
HalfIntegral Linkages in Highly Connected Directed Graphs
Abstract
We study the halfintegral kDirected Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NPcomplete even when restricted to instances where k=2, and the input graph is Lstrongly connected, for any L >= 1. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with k as part of the input).
Specifically, we show that there is an absolute constant c such that for each k >= 2 there exists L(k) such that 1/2 kDDPP is solvable in time O(V(G)^c) for a L(k)strongly connected directed graph G. As the function L(k) grows rather quickly, we also show that 1/2 kDDPP is solvable in time O(V(G)^{f(k)}) in (36k^3+2k)strongly connected directed graphs. We show that for each epsilon<1, deciding halfintegral feasibility of kDDPP instances is NPcomplete when k is given as part of the input, even when restricted to graphs with strong connectivity epsilon k.
BibTeX  Entry
@InProceedings{edwards_et_al:LIPIcs:2017:7876,
author = {Katherine Edwards and Irene Muzi and Paul Wollan},
title = {{HalfIntegral Linkages in Highly Connected Directed Graphs}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {36:136:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7876},
URN = {urn:nbn:de:0030drops78769},
doi = {10.4230/LIPIcs.ESA.2017.36},
annote = {Keywords: linkage, directed graph, treewidth}
}
01.09.2017
Keywords: 

linkage, directed graph, treewidth 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

01.09.2017 