2026-08-07T13:42:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8275 2024-03-06T10:41:46Z ddc:004 open_access

Faster Algorithms for Half-Integral T-Path Packing Babenko, Maxim Artamonov, Stepan graph algorithms multiflows path packings matchings 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 vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite 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 T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2, 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O(mn^1/2 log(n^2/m)/log(n)) time, thus matching the complexities of integral and half-integral versions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maxim Babenko and Stepan Artamonov 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.8 urn:nbn:de:0030-drops-82750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode