License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.5
URN: urn:nbn:de:0030-drops-176570
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17657/
Go to the corresponding LIPIcs Volume Portal

Akhmedov, Maxim ; Babenko, Maxim

Packing Odd Walks and Trails in Multiterminal Networks

pdf-format:
LIPIcs-STACS-2023-5.pdf (0.9 MB)

Abstract

Let G be an undirected network with a distinguished set of terminals T ⊆ V(G) and edge capacities cap: E(G) → ℝ_+. By an odd T-walk we mean a walk in G (with possible vertex and edge self-intersections) connecting two distinct terminals and consisting of an odd number of edges. Inspired by the work of Schrijver and Seymour on odd path packing for two terminals, we consider packings of odd T-walks subject to capacities cap.
First, we present a strongly polynomial time algorithm for constructing a maximum fractional packing of odd T-walks. For even integer capacities, our algorithm constructs a packing that is half-integer. Additionally, if cap(δ(v)) is divisible by 4 for any v ∈ V(G)-T, our algorithm constructs an integer packing.
Second, we establish and prove the corresponding min-max relation.
Third, if G is inner Eulerian (i.e. degrees of all nodes in V(G)-T are even) and cap(e) = 2 for all e ∈ E, we show that there exists an integer packing of odd T-trails (i.e. odd T-walks with no repeated edges) of the same value as in case of odd T-walks, and this packing can be found in polynomial time.
To achieve the above goals, we establish a connection between packings of odd T-walks and T-trails and certain multiflow problems in undirected and bidirected graphs.

BibTeX - Entry

@InProceedings{akhmedov_et_al:LIPIcs.STACS.2023.5,
  author =	{Akhmedov, Maxim and Babenko, Maxim},
  title =	{{Packing Odd Walks and Trails in Multiterminal Networks}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17657},
  URN =		{urn:nbn:de:0030-drops-176570},
  doi =		{10.4230/LIPIcs.STACS.2023.5},
  annote =	{Keywords: Odd path, signed and bidirected graph, multiflow, polynomial algorithm}
}

Keywords: Odd path, signed and bidirected graph, multiflow, polynomial algorithm
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

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