What question did this study set out to answer?

The aim is to develop efficient pseudodeterministic algorithms for the global minimum cut and minimum s-t cut problems.

January 25, 2026Open Access

Pseudodeterministic Algorithms for Minimum Cut Problems

Key Points

The aim is to develop efficient pseudodeterministic algorithms for the global minimum cut and minimum s-t cut problems.
Developed algorithms for global minimum cut and minimum s-t cut problems.
Analyzed running time compared to the fastest sequential deterministic algorithms.
Implemented algorithms in streaming, PRAM, and cut-query models.
Algorithm for global minimum cut shows better asymptotic running time than existing sequential algorithms.
Algorithms are applicable to models where no efficient deterministic solutions are known.

Abstract

In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.

Pseudodeterministic Algorithms for Minimum Cut Problems

Key Points

Abstract

Cite This Study