---
OA_place: repository
OA_type: green
_id: '21719'
abstract:
- lang: eng
  text: "We develop a new algorithmic framework for designing approximation algorithms
    for cut-based optimization problems on capacitated undirected graphs that undergo
    edge insertions and deletions. Specifically, our framework dynamically maintains
    a variant of the hierarchical \U0001D457-tree decomposition of [Madry FOCS’10],
    achieving a poly-logarithmic approximation factor to the graph’s cut structure
    and supporting edge updates in \U0001D442⁡(\U0001D45B\U0001D700) amortized update
    time, for any arbitrarily small constant \U0001D700 ∈(0,1).\r\nConsequently, we
    obtain new trade-offs between approximation and update/query time for fundamental
    cut-based optimization problems in the fully dynamic setting, including all-pairs
    minimum cuts, sparsest cut, multi-way cut, and multi-cut. For the last three problems,
    these trade-offs give the first fully-dynamic algorithms achieving poly-logarithmic
    approximation in sub-linear time per operation.\r\nThe main technical ingredient
    behind our dynamic hierarchy is a dynamic cut-sparsifier algorithm that can handle
    vertex splits with low recourse. This is achieved by white-boxing the dynamic
    cut sparsifier construction of [Abraham et al. FOCS’16], based on forest packing,
    together with new structural insights about the maintenance of these forests under
    vertex splits. Given the versatility of cut sparsification in both the static
    and dynamic graph algorithms literature, we believe this construction may be of
    independent interest."
acknowledgement: "Monika Henzinger: Funded by the European union. Views and opinions
  expressed\r\nare however those of the author(s) only and do not necessarily reflect
  those of the European Union or the European Research Council Executive Agency. Neither
  the European Union nor the granting authority can be held responsible for them.
  This project has received funding from the European Research Council (ERC) under
  the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,
  No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5982. For
  open access purposes, the author has applied a CC BY public copyright license to
  any author accepted manuscript version arising from this submission.\r\nPeter Kiss:
  This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/ESP6088024."
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Peter
  full_name: Kiss, Peter
  last_name: Kiss
- first_name: Ali
  full_name: Momeni, Ali
  last_name: Momeni
- first_name: Gernot
  full_name: Zöcklein, Gernot
  id: 45d5e826-47af-11f1-84e5-ba87c23fe681
  last_name: Zöcklein
citation:
  ama: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. Dynamic hierarchical
    j-tree decomposition and its applications. In: <i>Proceedings of the 2026 Annual
    ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026-January. Society for Industrial
    and Applied Mathematics; 2026:1128-1180. doi:<a href="https://doi.org/10.1137/1.9781611978971.45">10.1137/1.9781611978971.45</a>'
  apa: Goranci, G., Henzinger, M., Kiss, P., Momeni, A., &#38; Zöcklein, G. (2026).
    Dynamic hierarchical j-tree decomposition and its applications. In <i>Proceedings
    of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i> (Vol. 2026–January,
    pp. 1128–1180). Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611978971.45">https://doi.org/10.1137/1.9781611978971.45</a>
  chicago: Goranci, Gramoz, Monika Henzinger, Peter Kiss, Ali Momeni, and Gernot Zöcklein.
    “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” In <i>Proceedings
    of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i>, 2026–January:1128–80.
    Society for Industrial and Applied Mathematics, 2026. <a href="https://doi.org/10.1137/1.9781611978971.45">https://doi.org/10.1137/1.9781611978971.45</a>.
  ieee: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, and G. Zöcklein, “Dynamic hierarchical
    j-tree decomposition and its applications,” in <i>Proceedings of the 2026 Annual
    ACM SIAM Symposium on Discrete Algorithms</i>, 2026, vol. 2026–January, pp. 1128–1180.
  ista: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. 2026. Dynamic hierarchical
    j-tree decomposition and its applications. Proceedings of the 2026 Annual ACM
    SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms
    vol. 2026–January, 1128–1180.'
  mla: Goranci, Gramoz, et al. “Dynamic Hierarchical J-Tree Decomposition and Its
    Applications.” <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete
    Algorithms</i>, vol. 2026–January, Society for Industrial and Applied Mathematics,
    2026, pp. 1128–80, doi:<a href="https://doi.org/10.1137/1.9781611978971.45">10.1137/1.9781611978971.45</a>.
  short: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, G. Zöcklein, in:, Proceedings
    of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial
    and Applied Mathematics, 2026, pp. 1128–1180.
conference:
  name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2026-04-12T22:01:51Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-05-04T11:54:09Z
day: '07'
department:
- _id: MoHe
doi: 10.1137/1.9781611978971.45
ec_funded: 1
external_id:
  arxiv:
  - '2601.09139'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2601.09139
month: '01'
oa: 1
oa_version: Preprint
page: 1128-1180
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
  eissn:
  - '15579468'
  isbn:
  - '9781611978971'
  issn:
  - '10719040'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic hierarchical j-tree decomposition and its applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026-January
year: '2026'
...