The Minimum $k$-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k \ge 3$. Under the Max-Weight Clique conjecture, weighted Minimum $k$-Cut requires $n^{k-1-o(1)}$ time for every fixed $k$. The fastest previous...
The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\varepsilon)k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give...
Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs and evaluates the resulting conditional-expectation scores in two ways.
Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{supp}(A \star B)|$. We give a Las Vegas algorithm that computes $A \star B$ in $O(t \log t)$ expected time. More generally, for every $0<\delta \le \frac{1}{2}$, the algorithm terminates within $O(t \log t \log \frac{1}{\delta})$ tim...
Trevor Vaughn· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
