论文标题
流程授权II：无向图
Flow-augmentation II: Undirected graphs
论文作者
论文摘要
我们提出了最近引入的流量调节技术的无方向版本：给定一个无方向的多式$ g $，带有杰出的顶点$ s，t in v（g）$和一个整数$ k $，一个人可以在随机$ k^{o（1）} \ cdot（g）$ k^{o（g）$ + | + | e（g）$ seps a in Anit seps a seps a seps a seps a seps a。 \ binom {v（g）} {2} $使以下内容：对于最小的最小值$ st $ -cut $ s-cut $ z $ in $ g $ in $ g $，最多$ k $，$ z $，$ z $成为$ s $和$ s $ s $ s $和$ t $ t $ in $ s $ g+a $（即$ a $ a $ a $ a $ a $ a $ a） $ 2^{ - o（k \ log k）} $。 与有向图的版本[Stoc 2022]相比，此处介绍的版本提高了成功概率（$ 2^{ - O（k \ log k）} $，而不是$ 2^{ - o（k^4 \ log k）} $），对跑步时间的图表大小的线性依赖性，并且可以说是简单的。 直接推论是可以在无方向图上以随机fpt时间$ 2^{o（k \ log k）}（| v（g）|+| e（g）|）$ 2^{o（k \ log k）}以随机fpt时间$ 2^{o（k \ log k）}来解决。
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph $G$ with distinguished vertices $s,t \in V(G)$ and an integer $k$, one can in randomized $k^{O(1)} \cdot (|V(G)| + |E(G)|)$ time sample a set $A \subseteq \binom{V(G)}{2}$ such that the following holds: for every inclusion-wise minimal $st$-cut $Z$ in $G$ of cardinality at most $k$, $Z$ becomes a minimum-cardinality cut between $s$ and $t$ in $G+A$ (i.e., in the multigraph $G$ with all edges of $A$ added) with probability $2^{-O(k \log k)}$. Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability ($2^{-O(k \log k)}$ instead of $2^{-O(k^4 \log k)}$), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective $st$-Cut problem can be solved in randomized FPT time $2^{O(k \log k)} (|V(G)|+|E(G)|)$ on undirected graphs.
