Description:
<jats:p>
We present an undirected version of the recently introduced
<jats:italic>flow-augmentation</jats:italic>
technique: Given an undirected multigraph
<jats:italic>G</jats:italic>
with distinguished vertices
<jats:italic>s,t ∈ V(G)</jats:italic>
and an integer
<jats:italic>k</jats:italic>
, one can in randomized
<jats:italic>k</jats:italic>
<jats:sup>𝒪(1)</jats:sup>
⋅
<jats:italic>(|V(G)| + |E(G)|)</jats:italic>
time sample a set
<jats:italic>A</jats:italic>
⊆
<jats:inline-formula content-type="math/tex">
<jats:tex-math notation="LaTeX" version="MathJax">\(\binom{V(G)}{2}\)</jats:tex-math>
</jats:inline-formula>
such that the following holds: for every inclusion-wise minimal
<jats:italic>st</jats:italic>
-cut
<jats:italic>Z</jats:italic>
in
<jats:italic>G</jats:italic>
of cardinality at most
<jats:italic>k</jats:italic>
,
<jats:italic>Z</jats:italic>
becomes a
<jats:italic>minimum-cardinality</jats:italic>
cut between
<jats:italic>s</jats:italic>
and
<jats:italic>t</jats:italic>
in
<jats:italic>G+A</jats:italic>
(i.e., in the multigraph
<jats:italic>G</jats:italic>
with all edges of
<jats:italic>A</jats:italic>
added) with probability 2
<jats:sup>
-𝒪(
<jats:italic>k</jats:italic>
log
<jats:italic>k</jats:italic>
</jats:sup>
).
</jats:p>
<jats:p>
Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2
<jats:sup>
-𝒪(
<jats:italic>k</jats:italic>
log
<jats:italic>k</jats:italic>
</jats:sup>
) instead of 2
<jats:sup>
-𝒪(
<jats:italic>
k
<jats:sup>4</jats:sup>
</jats:italic>
log
<jats:italic>k</jats:italic>
)
</jats:sup>
), linear dependency on the graph size in the running time bound, and an arguably simpler proof.
</jats:p>
<jats:p>
An immediate corollary is that the
<jats:sc>
Bi-objective
<jats:italic>st</jats:italic>
-Cut
</jats:sc>
problem can be solved in randomized FPT time 2
<jats:sup>
𝒪(
<jats:italic>k</jats:italic>
log
<jats:italic>k</jats:italic>
)
</jats:sup>
<jats:italic>(|V(G)|+|E(G)|)</jats:italic>
on undirected graphs.
</jats:p>