Multi-budgeted Directed Cuts
Multi-budgeted Directed Cuts
复制标题
DOI：
10.1007/s00453-019-00609-1
复制
发表时间：
2018-10
期刊：
影响因子：
1.1
通讯作者：
Stefan Kratsch;Shaohua Li;D. Marx;Marcin Pilipczuk;Magnus Wahlström
中科院分区：
文献类型：
--
作者：
Stefan Kratsch;Shaohua Li;D. Marx;Marcin Pilipczuk;Magnus Wahlström
在本文中，我们研究了多预算的经典最小割问题和图分离问题，原来是重要的参数化复杂性的变种：斜MulticutandDirected反馈弧集。在我们的推广中，我们为一些边分配颜色，并为颜色提供单独的颜色。对于每种颜色，设为颜色i的边集。图分离问题的多预算变体的解决方案不仅需要满足通常的分离要求（即，分别是割、斜多割或定向反馈弧集），但也需要满足对于每个。与经典的最小割问题相反，多预算变量即使对于。针对这三个问题，我们提出了参数化的FPT算法.为此，我们开发了一个分支程序的多预算的最小割问题，衡量的进展，算法不是通过reducingkas通常，但提高了一些边缘的能力，从而增加了最大的源到汇流的大小。使用一个类似的策略是用来枚举一个给定的大小的所有重要的分隔符的事实，我们合并这个过程与流引导的分支，并显示FPT绑定的数量（适当定义）重要的多预算分隔符。这使我们能够将我们的算法扩展到斜多割和定向反馈弧集问题。此外，我们显示连接的多预算变量与加权变量的定向切割问题和chain-SAT问题，其参数化的复杂性仍然是一个开放的问题。我们表明，这些问题承认一个有界的参数数量的“最大限度地推动”的解决方案（在类似的精神，重要的分离器最大限度地推动），给他们的易处理性有些弱的证据。
In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity:Skew MulticutandDirected Feedback Arc Set. In our generalization, we assign colorsto some edges and give separate budgetsfor colors. For every color, letbe the set of edges of colori. The solutionCfor the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy thatfor every. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for. We propose FPT algorithms parameterized byfor all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducingkas usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to theSkew MulticutandDirected Feedback Arc Setproblems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and theChain-SATproblem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of “maximally pushed” solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.