Solving hard cut problems via flow-augmentation
Solving hard cut problems via flow-augmentation
复制标题
通过流量增强解决硬切割问题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Magnus Wahlström
中科院分区：
文献类型：
--
作者：
Eun Jung Kim;Stefan Kratsch;Marcin Pilipczuk;Magnus Wahlström
针对无向图中的图割问题，我们提出了一种新的设计FPT算法的方法，我们称之为流增强。我们的技巧适用于在具有指定终点$S$和$t$的无向图$G$中寻找至多$k$的(边)$(S，t)$割的问题。
更确切地说，我们考虑这样的问题：其中(未知)解是至多有$k$大小的集合$Z子集E(G)$，使得(1)在$G-Z$中，$S$和$t$是不同的连通分支，(2)$Z$的每条边都连接着$G-Z$的两个不同的连通分支，以及(3)如果我们定义集合$Z_{S，t}子集Z$是Z$中存在$(S，t)$路径$P_e$且具有$E(P_E)帽Z={e}$的$Z_{S，T}$将$S$与$t$分开。我们证明了在这种情形下，可以在随机时间$k^{O(1)}(|V(G)|+|E(G)|)$向图中添加多条边，使得对于$2^{-O(k对数k)}$概率，不存在任何附加边连接$G-Z$和$Z_{S，t}$成为$S$和$t$之间的最小割。
我们将我们的方法应用于一个臭名昭著的“顽固”图割问题的随机化的FPT算法，我们称之为耦合最小割。这个问题源于对最小CSP问题的FPT算法的研究，而不适用于图割问题中的其他参数化算法，如随机收缩、树宽缩减或阴影消除。
为了证明该方法的有效性，我们考虑了更一般的Min SAT($Gamma$)，它由解决方案成本来参数化。我们证明了每个问题Min SAT($Gamma$)要么是(1)FPT，(2)W[1]-Hard，要么是(3)能够表示软约束$(U O V)$，从而也是有向图中的最小割问题。所有的W[1]-困难情形都是已知的或直接的，主要的新结果是一种推广的耦合最小割集的FPT算法。
We present a new technique for designing FPT algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s,t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals $s$ and $t$.
More precisely, we consider problems where an (unknown) solution is a set $Z subseteq E(G)$ of size at most $k$ such that (1) in $G-Z$, $s$ and $t$ are in distinct connected components, (2) every edge of $Z$ connects two distinct connected components of $G-Z$, and (3) if we define the set $Z_{s,t} subseteq Z$ as these edges $e in Z$ for which there exists an $(s,t)$-path $P_e$ with $E(P_e) cap Z = {e}$, then $Z_{s,t}$ separates $s$ from $t$. We prove that in this scenario one can in randomized time $k^{O(1)} (|V(G)|+|E(G)|)$ add a number of edges to the graph so that with $2^{-O(k log k)}$ probability no added edge connects two components of $G-Z$ and $Z_{s,t}$ becomes a minimum cut between $s$ and $t$.
We apply our method to obtain a randomized FPT algorithm for a notorious "hard nut" graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems, and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal.
To demonstrate the power of the approach, we consider more generally Min SAT($Gamma$), parameterized by the solution cost. We show that every problem Min SAT($Gamma$) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint $(u o v)$, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut.
影响因子：
1.1
作者：
Stefan Kratsch;Shaohua Li;D. Marx;Marcin Pilipczuk;Magnus Wahlström
通讯作者：
Stefan Kratsch;Shaohua Li;D. Marx;Marcin Pilipczuk;Magnus Wahlström
通用价值 CSP 的复杂性
DOI：
10.1109/focs.2015.80
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Kolmogorov V
通讯作者：
Kolmogorov V