带权最大割问题的一种基于划分技术的固定参数可解算法

运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行1n(1/ε)]×2~k(0ε1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(1n(1/ε)2~k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2~(2k+12log~2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的。

Fixed-parameter tractable algorithms based on partition for the weighted maximum cut problem

This paper studies the weighted maximum cut problem in terms of the parameterized computational complexity theory. After defining the parameterized version of the problem, the paper presents a randomized algorithm based on random separation for the parameterized problem. The algorithm randomly bipartitions the vertex set of a given instance for 「 ln (1/ε)」×2~k (0<ε<1) times, and returns a k cut of maximum weight as the output, so that it can obtain the solution with the probability of at least 1-ε in time O~*( ln (1/ε)2~k).On the basis of the study above, the paper also proposes a deterministic parameterized algorithm with the time complexity of O~*(2~（2k+12log~2(2k)) by mainly employing the recent improved ( n,k ) universal set techniques, which shows that the maximum cut problem is fixed parameter tractable.