Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions

摘要

In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O(na <...2.619 (r/(1-4r))+n (3)), where n is the number of vertices and r=k. Particularly, the time complexity is O (au)(2.619 (k) ) for kao(n (2)) and polynomial for kaO(nlogn), which implies that the problem can be solved in subexponential time for kao(n (2)). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For kao(n (3)), the algorithm runs in subexponential O(n (3)a <...5.171 (theta) ) time, where .