A simple deterministic algorithm is given that finds a global minimum cut using $\tilde O(\min\left\{ n\delta,n^2/\delta \right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $\delta$ is the minimum degree of the graph.
Abstract
Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ n\delta,n^2/\delta \right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $\delta$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $\delta$.
We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving th...
Henry L. Fleischmann, Jason Li, Thatchaphol Saranurak et al.· 3 citations· ⚡1
The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\al...
The deterministic algorithm represents a $\tilde{O}(\Delta)$ improvement on span and $\tilde{O}(\Delta^2)$ on work compared to their algorithm, and the randomized algorithm improves the span and work by $\tilde{O}(\Delta^2)$ and $\tilde{O}(\Delta^3)$ factors, respectively.
Jeremy T. Fineman, Seyed Ali Mohammadi· 0 citations
We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $\Omega((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very r...
This work proposes an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{3/2}\eps^{-1})$ time and matches the best known size of the determinant sparsifiers.
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an app...
Zhao Song· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.