论文标题
关于加权图分离问题和流程
On weighted graph separation problems and flow-augmentation
论文作者
论文摘要
最近引入的\ emph {flow-ageagmentation} [Kim等人，stoc 2022]的第一个应用之一是\ textsc {定向反馈顶点set}加权版本的固定参数算法，这是一个具有里程碑意义的问题，它是参数化的复杂性。在本说明中，我们探索了流动效能对其他加权图分离问题的适用性，该问题通过切割的大小参数化。我们显示以下内容。 - 在加权的无向图中\ textsc {multi-ut}是fpt，无论是在边缘和顶点删除版本中。 - \ textsc {组反馈顶点集的加权版本即使是Oracle对组操作的访问，也是FPT。 - \ textsc {有向子集反馈顶点集的加权版本是fpt。我们的研究揭示了\ textsc {定向对称多图}是下一个重要的图形分离问题，即使在未加权的环境中，参数化的复杂性仍然未知。
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterized complexity. In this note we explore applicability of flow-augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following. -- In weighted undirected graphs \textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an oracle access to group operations. -- The weighted version of \textsc{Directed Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed Symmetric Multicut} as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.
