论文标题
关于对称的有向多刺的参数化复杂性
On the parameterized complexity of symmetric directed multicut
论文作者
论文摘要
我们从参数化的复杂性角度研究了问题对称的多速。在此问题中，输入是digraph $ d $，一组剪切请求$ c = \ {（s_1，t_1），\ ldots，（s_ \ ell，t_ \ ell）\} $和一个整数$ k $ \ ell $，$ x $相交所有$（s_i，t_i）$ - 路径或所有$（t_i，s_i）$ - 路径。同等地，$ d-x $的每个紧密连接的组件最多包含$ s_i $中的一个顶点，每个$ i $中的$ s_i $和$ t_i $。以前从近似算法的研究中知道了这个问题，其中已知它具有$ O（\ log k \ log \ log \ log k）$ - 近似。我们注意到，该问题通过$ k $进行了参数，直接概括了多个有趣的FPT问题，例如（无向）顶点多速和有向子集反馈顶点集。我们无法纯粹通过$ k $进行参数化的fpt算法的存在，但是我们给出了三个部分结果：由$ k+\ ell $参数化的fpt算法；由$ k $参数的FPT时间2-Approximation;以及由$ k $参数的FPT算法，用于剪切请求形成一个集团，对称的对称的多路切割的特殊情况。纯粹由$ k $参数化的FPT算法的存在仍然是一种有趣的开放可能性。
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a set $X \subseteq V(D)$ of size at most $k$ such that for every $1 \leq i \leq \ell$, $X$ intersects either all $(s_i,t_i)$-paths or all $(t_i,s_i)$-paths. Equivalently, every strongly connected component of $D-X$ contains at most one vertex out of $s_i$ and $t_i$ for every $i$. This problem is previously known from research in approximation algorithms, where it is known to have an $O(\log k \log \log k)$-approximation. We note that the problem, parameterized by $k$, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by $k$, but we give three partial results: An FPT algorithm parameterized by $k+\ell$; an FPT-time 2-approximation parameterized by $k$; and an FPT algorithm parameterized by $k$ for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by $k$ remains an intriguing open possibility.
