Babenko, Maxim ;
Artamonov, Stepan
Faster Algorithms for HalfIntegral TPath Packing
Abstract
Let G = (V, E) be an undirected graph, a subset of vertices T be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertexdisjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum nonbipartite matching and thus gives an O(mn^1/2 log(n^2/m)/log(n))time algorithm (hereinafter n := V, m := E).
Now let us consider the fractional relaxation, i.e. allow Tpath packings with arbitrary nonnegative real weights. It is known that there always exists a halfintegral solution, that is, one only needs to assign weights 0, 1/2, 1 to maximize the total weight of Tpaths. It is also known that an optimum halfintegral packing can be found in stronglypolynomial time but the actual time bounds are far from being satisfactory.
In this paper we present a novel algorithm that solves the halfintegral problem within O(mn^1/2 log(n^2/m)/log(n)) time, thus matching the complexities of integral and halfintegral versions.
BibTeX  Entry
@InProceedings{babenko_et_al:LIPIcs:2017:8275,
author = {Maxim Babenko and Stepan Artamonov},
title = {{Faster Algorithms for HalfIntegral TPath Packing}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {8:18:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8275},
URN = {urn:nbn:de:0030drops82750},
doi = {10.4230/LIPIcs.ISAAC.2017.8},
annote = {Keywords: graph algorithms, multiflows, path packings, matchings}
}
07.12.2017
Keywords: 

graph algorithms, multiflows, path packings, matchings 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 