License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.13
URN: urn:nbn:de:0030-drops-99613
URL: http://drops.dagstuhl.de/opus/volltexte/2018/9961/
Go to the corresponding LIPIcs Volume Portal


Preißer, Johanna E. ; Schmidt, Jens M.

Computing Vertex-Disjoint Paths in Large Graphs Using MAOs

pdf-format:
LIPIcs-ISAAC-2018-13.pdf (0.4 MB)


Abstract

We consider the problem of computing k in N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, O(min{k,sqrt{n}}m) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every 1 <= k <= delta (where delta is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last delta-k+2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time O(m), which improves the previously best time O(min{k,sqrt{n}}m). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.

BibTeX - Entry

@InProceedings{preier_et_al:LIPIcs:2018:9961,
  author =	{Johanna E. Prei{\ss}er and Jens M. Schmidt},
  title =	{{Computing Vertex-Disjoint Paths in Large Graphs Using MAOs}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9961},
  URN =		{urn:nbn:de:0030-drops-99613},
  doi =		{10.4230/LIPIcs.ISAAC.2018.13},
  annote =	{Keywords: Computing Disjoint Paths, Large Graphs, Vertex-Connectivity, Linear-Time, Maximal Adjacency Ordering, Maximum Cardinality Search, Big Data, Certifying}
}

Keywords: Computing Disjoint Paths, Large Graphs, Vertex-Connectivity, Linear-Time, Maximal Adjacency Ordering, Maximum Cardinality Search, Big Data, Certifying
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 27.11.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI