Search Results

Documents authored by Babenko, Maxim

Document
DOI: 10.4230/LIPIcs.STACS.2023.5
Packing Odd Walks and Trails in Multiterminal Networks

Authors: Maxim Akhmedov and Maxim Babenko

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

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.
Cite as

Maxim Akhmedov and Maxim Babenko. Packing Odd Walks and Trails in Multiterminal Networks. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.STACS.2023.5},
  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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.8
Faster Algorithms for Half-Integral T-Path Packing

Authors: Maxim Babenko and Stepan Artamonov

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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 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.
Cite as

Maxim Babenko and Stepan Artamonov. Faster Algorithms for Half-Integral T-Path Packing. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{babenko_et_al:LIPIcs.ISAAC.2017.8,
  author =	{Babenko, Maxim and Artamonov, Stepan},
  title =	{{Faster Algorithms for Half-Integral T-Path Packing}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{8:1--8:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.8},
  URN =		{urn:nbn:de:0030-drops-82750},
  doi =		{10.4230/LIPIcs.ISAAC.2017.8},
  annote =	{Keywords: graph algorithms, multiflows, path packings, matchings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.519
New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs

Authors: Maxim Babenko and Alexey Gusakov

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
By a T-star we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G. For example, we get ordinary matchings for $T = 1$ and packings of paths of length 1 and 2 for $T = 2$. Hereinafter we assume that T >= 2. Hell and Kirkpatrick devised an ad-hoc augmenting algorithm that finds a T-star packing covering the maximum number of nodes. The latter algorithm also yields a min-max formula. We show that T-star packings are reducible to network flows, hence the above problem is solvable in $O(m sqrt(n))$ time (hereinafter n denotes the number of nodes in G, and m --- the number of edges). For the edge-weighted case (in which weights may be assumed positive) finding a maximum $T$-packing is NP-hard. A novel 9/4 T/(T + 1)-factor approximation algorithm is presented. For non-negative node weights the problem reduces to a special case of a max-cost flow. We develop a divide-and-conquer approach that solves it in O(m sqrt(n) log(n)) time. The node-weighted problem with arbitrary weights is more difficult. We prove that it is NP-hard for T >= 3 and is solvable in strongly-polynomial time for T = 2.
Cite as

Maxim Babenko and Alexey Gusakov. New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 519-530, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{babenko_et_al:LIPIcs.STACS.2011.519,
  author =	{Babenko, Maxim and Gusakov, Alexey},
  title =	{{New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{519--530},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.519},
  URN =		{urn:nbn:de:0030-drops-30402},
  doi =		{10.4230/LIPIcs.STACS.2011.519},
  annote =	{Keywords: graph algorithms, approximation algorithms, generalized matchings, flows, weighted packings}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact