Preißer, Johanna E. ;
Schmidt, Jens M.
Computing VertexDisjoint Paths in Large Graphs Using MAOs
Abstract
We consider the problem of computing k in N internally vertexdisjoint 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 flowbased 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 vertexdisjoint paths between every pair of the last deltak+2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently nonconstructive.
We present the first algorithm that computes these k internally vertexdisjoint 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 VertexDisjoint Paths in Large Graphs Using MAOs}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {13:113:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9961},
URN = {urn:nbn:de:0030drops99613},
doi = {10.4230/LIPIcs.ISAAC.2018.13},
annote = {Keywords: Computing Disjoint Paths, Large Graphs, VertexConnectivity, LinearTime, Maximal Adjacency Ordering, Maximum Cardinality Search, Big Data, Certifying}
}
2018
Keywords: 

Computing Disjoint Paths, Large Graphs, VertexConnectivity, LinearTime, 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: 

2018 