A more effective linear kernelization for cluster editing

被引:68
作者
Guo, Jiong [1 ]
机构
[1] Univ Jena, Inst Informat, D-07743 Jena, Germany
关键词
Combinatorial problems; Fixed-parameter tractability; Computational biology; Preprocessing; Data reduction; DECOMPOSITION; ALGORITHMS;
D O I
10.1016/j.tcs.2008.10.021
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In the NP-hard CLUSTER EDITING problem, we have as input an undirected graph G and an integer k >= 0. The question is whether we can transform G, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for CLUSTER EDITING that leads to a problem kernel with at most 6k vertices. More precisely, we present a cubic-time algorithm that, given a graph G and an integer k >= 0, finds a graph G' and an integer k' >= k such that G can be transformed into a cluster graph by at most k edge modifications iff G' can be transformed into a cluster graph by at most k' edge modifications, and the problem kernel G' has at most 6k vertices. So far, only a problem kernel of 24k vertices was known. Second, we show that this bound for the number of vertices of G' can be further improved to 4k vertices. Finally, we consider the variant Of CLUSTER EDITING where the number of cliques that the cluster graph can contain is stipulated to be a constant d > 0. We present a simple kernelization for this variant leaving a problem kernel of at most (d + 2)k + d vertices. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:718 / 726
页数:9
相关论文
共 27 条
[1]  
Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI DOI 10.1145/1060590.1060692
[2]   Polynomial-time data reduction for DOMINATING SET [J].
Alber, J ;
Fellows, MR ;
Niedermeier, R .
JOURNAL OF THE ACM, 2004, 51 (03) :363-384
[3]   Correlation clustering [J].
Bansal, N ;
Blum, A ;
Chawla, S .
MACHINE LEARNING, 2004, 56 (1-3) :89-113
[4]   Clustering gene expression patterns [J].
Ben-Dor, A ;
Shamir, R ;
Yakhini, Z .
JOURNAL OF COMPUTATIONAL BIOLOGY, 1999, 6 (3-4) :281-297
[5]  
BOCKER S, 2008, SERIES ADV BIOINFORM, V5, P211
[6]  
Böcker S, 2008, LECT NOTES COMPUT SC, V5165, P1
[7]  
Boecker S, 2008, LECT NOTES COMPUT SC, V5038, P289, DOI 10.1007/978-3-540-68552-4_22
[8]   Clustering with qualitative information [J].
Charikar, M ;
Guruswami, V ;
Wirth, A .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (03) :360-383
[9]   Parametric duality and kernelization: Lower bounds and upper bounds on kernel size [J].
Chen, Jianer ;
Fernau, Henning ;
Kanj, Iyad A. ;
Xia, Ge .
SIAM JOURNAL ON COMPUTING, 2007, 37 (04) :1077-1106
[10]   Computing phylogenetic roots with bounded degrees and errors [J].
Chen, ZZ ;
Jiang, T ;
Lin, GH .
SIAM JOURNAL ON COMPUTING, 2003, 32 (04) :864-879