betaFeedback

WorksComputer Science

Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs

Abstract

We determine the dense worst-case quantum query complexity of exact minimum multicut on simple unweighted undirected graphs. With at most kk explicit demand pairs, our adjacency-array algorithm uses \OO(n+\min\{m,n^{3/2}\sqrt{k}\}) queries; a matching lower bound holds for every 1≤k≤⌊n/2⌋1\le k\le\lfloor n/2\rfloor and sufficiently large nn, with constants uniform in kk. In particular, the k=1k=1 case gives an \OO(n^{3/2}) query algorithm for prescribed ss–tt cut. The upper bound combines degree-sensitive spectral estimates of local improvement with refinement by unions of label classes. These steps retain every original optimum and permit exact acquisition without an additional label-count factor. Separately, we prove an Ω(n3/2)Ω(n^{3/2}) global minimum-cut lower bound on dense connected graphs, matching the existing upper bound up to polylogarithmic factors. It holds for the value and for any optimum shore, even with known degrees and sorted neighbor arrays; regular hard instances have balanced optimum cuts. Both lower bounds use degree-preserving switches and classify optimum outputs across a hidden threshold. Our upper bound concerns input queries, not total running time: computation on acquired data may be exponential, even in the single-demand case. Matching bounds at each prescribed sparse edge count are not established.

Paper details

vlnc:W_452j59wc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…