---
OA_place: repository
OA_type: green
_id: '21720'
abstract:
- lang: eng
  text: "We present an exact fully-dynamic minimum cut algorithm that runs in \U0001D45B\U0001D45C⁡(1)
    deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−\U0001D450⁡\U0001D45B)
    for any \U0001D450 >0, improving on the previous algorithm of Jin, Sun, and Thorup
    (SODA 2024) whose minimum cut size limit is (log⁡\U0001D45B)\U0001D45C⁡(1). Combined
    with graph sparsification, we obtain the first (1 +\U0001D716)-approximate fully-dynamic
    minimum cut algorithm on weighted graphs, for any \U0001D716 ≥2−Θ⁡(log3/4−\U0001D450⁡\U0001D45B),
    in \U0001D45B\U0001D45C⁡(1) randomized update time.\r\nOur main technical contribution
    is a deterministic local minimum cut algorithm, which replaces the randomized
    LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025)."
acknowledgement: Funded by the European union. Views and opinions expressed are 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
  full_name: El-Hayek, Antoine
  id: 888a098e-fcac-11ee-aff7-d347be57b725
  last_name: El-Hayek
  orcid: 0000-0003-4268-7368
- 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: Jason
  full_name: Li, Jason
  last_name: Li
citation:
  ama: 'El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum
    cut of superpolylogarithmic size in subpolynomial time. In: <i>Proceedings of
    the Annual ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026. Society for
    Industrial and Applied Mathematics; 2026:613-663. doi:<a href="https://doi.org/10.1137/1.9781611978971.25">10.1137/1.9781611978971.25</a>'
  apa: 'El-Hayek, A., Henzinger, M., &#38; Li, J. (2026). Deterministic and exact
    fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time.
    In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>
    (Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied
    Mathematics. <a href="https://doi.org/10.1137/1.9781611978971.25">https://doi.org/10.1137/1.9781611978971.25</a>'
  chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact
    Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.”
    In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>,
    2026:613–63. Society for Industrial and Applied Mathematics, 2026. <a href="https://doi.org/10.1137/1.9781611978971.25">https://doi.org/10.1137/1.9781611978971.25</a>.
  ieee: A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic
    minimum cut of superpolylogarithmic size in subpolynomial time,” in <i>Proceedings
    of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, Vancouver, Canada,
    2026, vol. 2026, pp. 613–663.
  ista: 'El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic
    minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of
    the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
    Algorithms vol. 2026, 613–663.'
  mla: El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut
    of Superpolylogarithmic Size in Subpolynomial Time.” <i>Proceedings of the Annual
    ACM SIAM Symposium on Discrete Algorithms</i>, vol. 2026, Society for Industrial
    and Applied Mathematics, 2026, pp. 613–63, doi:<a href="https://doi.org/10.1137/1.9781611978971.25">10.1137/1.9781611978971.25</a>.
  short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM
    Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
    2026, pp. 613–663.
conference:
  end_date: 2026-01-14
  location: Vancouver, Canada
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2026-01-11
date_created: 2026-04-12T22:01:51Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-05-04T11:36:47Z
day: '07'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1137/1.9781611978971.25
ec_funded: 1
external_id:
  arxiv:
  - '2512.13105'
intvolume: '      2026'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2512.13105
month: '01'
oa: 1
oa_version: Preprint
page: 613-663
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 Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - '9781611978971'
  eissn:
  - 1557-9468
  issn:
  - 1071-9040
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size
  in subpolynomial time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026
year: '2026'
...