---
OA_place: repository
OA_type: free access
_id: '18503'
abstract:
- lang: eng
  text: "In 1996, Karger [Kar96] gave a startling randomized algorithm that finds
    a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear
    time meaning linear (in the size of the input) times a polylogarthmic factor.
    In this paper, we give the first deterministic algorithm which runs in near-linear
    time for weighted graphs.\r\nPreviously, the breakthrough results of Kawarabayashi
    and Thorup [KT19] gave a near-linear time algorithm for simple graphs (which was
    improved to have running time O(m log2 n log log n) in [HRW20].) The main technique
    here is a clustering procedure that perfectly preserves minimum cuts. Recently,
    Li [Li21] gave an m1+o(1) deterministic minimum-cut algorithm for weighted graphs;
    this form of running time has been termed “almost-linear”. Li uses almost-linear
    time deterministic expander decompositions which do not perfectly preserve minimum
    cuts, but he can use these clusterings to, in a sense, “derandomize” the methods
    of Karger.\r\nIn terms of techniques, we provide a structural theorem that says
    there exists a sparse clustering that preserves minimum cuts in a weighted graph
    with o(1) error. In addition, we construct it deterministically in near linear
    time. This was done exactly for simple graphs in [KT19, HRW20] and with polylogarithmic
    error for weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20]
    to weighted graphs presents significant challenges, and moreover, the algorithm
    can only polylogarithmically approximately preserve minimum cuts. A remaining
    challenge is to reduce the polylogarithmic-approximate clusterings to 1 + o(1/
    log n)-approximate so that they can be applied recursively as in [Li21] over O(log
    n) many levels. This is an additional challenge that requires building on properties
    of tree-packings in the presence of a wide range of edge weights to, for example,
    find sources for local flow computations which identify minimum cuts that cross
    clusters."
acknowledgement: This project has received funding from the European Research Council(ERC)
  under the European Union’s Horizon 2020 research and innovation programme (Grant
  agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDyn-Struct)”
  and the Austrian Science Fund (FWF) project Z 422-N, project “Static and Dynamic
  Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a
  Reactive Network Layer (ReactNet)”, P33775-N, with additional funding from the netidee
  SCIENCE Stiftung, 2020–2024.
article_processing_charge: No
arxiv: 1
author:
- 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
- first_name: Satish
  full_name: Rao, Satish
  last_name: Rao
- first_name: Di
  full_name: Wang, Di
  last_name: Wang
citation:
  ama: 'Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut
    in weighted graphs. In: <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>.
    Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:<a href="https://doi.org/10.1137/1.9781611977912.111">10.1137/1.9781611977912.111</a>'
  apa: 'Henzinger, M., Li, J., Rao, S., &#38; Wang, D. (2024). Deterministic near-linear
    time minimum cut in weighted graphs. In <i>35th Annual ACM-SIAM Symposium on Discrete
    Algorithms</i> (pp. 3089–3139). Alexandria, VA,  United States: Society for Industrial
    and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611977912.111">https://doi.org/10.1137/1.9781611977912.111</a>'
  chicago: Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear
    Time Minimum Cut in Weighted Graphs.” In <i>35th Annual ACM-SIAM Symposium on
    Discrete Algorithms</i>, 3089–3139. Society for Industrial and Applied Mathematics,
    2024. <a href="https://doi.org/10.1137/1.9781611977912.111">https://doi.org/10.1137/1.9781611977912.111</a>.
  ieee: M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time
    minimum cut in weighted graphs,” in <i>35th Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>, Alexandria, VA,  United States, 2024, pp. 3089–3139.
  ista: 'Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum
    cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms.
    SODA: Symposium on Discrete Algorithms, 3089–3139.'
  mla: Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted
    Graphs.” <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society
    for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:<a href="https://doi.org/10.1137/1.9781611977912.111">10.1137/1.9781611977912.111</a>.
  short: M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium
    on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024,
    pp. 3089–3139.
conference:
  end_date: 2024-01-10
  location: Alexandria, VA,  United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2024-01-07
corr_author: '1'
date_created: 2024-11-04T10:54:21Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2025-06-24T12:09:26Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977912.111
ec_funded: 1
external_id:
  arxiv:
  - '2401.05627'
fulldoi: https://doi.org/10.1137/1.9781611977912.111
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2401.05627
month: '01'
oa: 1
oa_version: Preprint
page: 3089-3139
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: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: 35th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic near-linear time minimum cut in weighted graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...