DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.36

Half-Integral Linkages in Highly Connected Directed Graphs

Authors: Katherine Edwards, Irene Muzi, and Paul Wollan

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We study the half-integral k-Directed Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where k=2, and the input graph is L-strongly 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 half-integral feasibility of kDDPP instances is NP-complete when k is given as part of the input, even when restricted to graphs with strong connectivity epsilon k.

Cite as

Katherine Edwards, Irene Muzi, and Paul Wollan. Half-Integral Linkages in Highly Connected Directed Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{edwards_et_al:LIPIcs.ESA.2017.36,
  author =	{Edwards, Katherine and Muzi, Irene and Wollan, Paul},
  title =	{{Half-Integral Linkages in Highly Connected Directed Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.36},
  URN =		{urn:nbn:de:0030-drops-78769},
  doi =		{10.4230/LIPIcs.ESA.2017.36},
  annote =	{Keywords: linkage, directed graph, treewidth}
}

Search Results

Documents authored by Wollan, Paul

Half-Integral Linkages in Highly Connected Directed Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message