Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable
Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable
复制标题
DOI：
10.4230/lipics.icalp.2018.112
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mingyu Xiao;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Mingyu Xiao;H. Nagamochi
在有界度割问题中，给定一个多重图G =（V，E），两个不相交的顶点子集A，B ∈ V，两个函数uA，uB：V → {0，1，. . . , |E|}，且整数k ≥ 0。本文的任务是确定是否存在一个最小的（A，B）-割（VA，VB），其大小至多为k，使得导出子图G[VA]中每个顶点v ∈ VA的度至多为uA（v），导出子图G[VB ]中每个顶点v ∈ VB的度至多为u B（v）.在本文中，我们通过给出一个218 k，证明了有界度割问题是固定参数易处理的。|G|时间复杂度为O（1）这是该问题的第一个单指数FPT算法。该算法的核心是基于重要割的两个新引理，给出了满足某些性质的最小割的一部分顶点子集的候选个数的上界。这些引理可以用来设计固定参数的易处理的算法，为更多的相关问题。2012年ACM学科分类计算理论→固定参数易处理性、计算数学→图算法
In the bounded-degree cut problem, we are given a multigraph G = (V,E), two disjoint vertex subsets A,B ⊆ V , two functions uA,uB : V → {0, 1, . . . , |E|} on V , and an integer k ≥ 0. The task is to determine whether there is a minimal (A,B)-cut (VA, VB) of size at most k such that the degree of each vertex v ∈ VA in the induced subgraph G[VA] is at most uA(v) and the degree of each vertex v ∈ VB in the induced subgraph G[VB ] is at most uB(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 218k|G|O(1)-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems. 2012 ACM Subject Classification Theory of computation→ Fixed parameter tractability, Mathematics of computing → Graph algorithms