zbMATH — the first resource for mathematics

A more effective linear kernelization for cluster editing. (English) Zbl 1162.68025
Summary: In the NP-hard Cluster Editing problem, we have as input an undirected graph \(G\) and an integer \(k\geq 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 M. Fellows [“The lost continent of polynomial time: Preprocessing and kernelization”, Lect. Notes Comput. Sci. 4169, 276–277 (2006; Zbl 1154.68560)] 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\geq 0\), finds a graph \(G{^{\prime}}\) and an integer \(k{^{\prime}}\leq k\) such that \(G\) can be transformed into a cluster graph by at most \(k\) edge modifications iff \(G{^{\prime}}\) can be transformed into a cluster graph by at most \(k{^{\prime}}\) edge modifications, and the problem kernel \(G{^{\prime}}\) 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{^{\prime}}\) can be further improved to 4\(k\) 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.

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
92-08 Computational methods for problems pertaining to biology
Full Text: DOI
[1] Ailon, N.; Charikar, M.; Newman, A., Aggregating inconsistent information: ranking and clustering, (), 684-693 · Zbl 1192.90252
[2] Alber, J.; Fellows, M.R.; Niedermeier, R., Polynomial time data reduction for dominating set, Journal of the ACM, 51, 3, 363-384, (2004) · Zbl 1192.68337
[3] Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi, Correlation clustering, Machine learning, 56, 1, 89-113, (2004) · Zbl 1089.68085
[4] Ben-Dor, A.; Shamir, R.; Yakhini, Z., Clustering gene expression patterns, Journal of computational biology, 6, 3/4, 281-297, (1999)
[5] Böcker, S.; Briesemeister, S.; Bui, Q.B.A.; Truß, A., A fixed-parameter approach for weighted cluster editing, (), 211-220 · Zbl 1178.68373
[6] Böcker, S.; Briesemeister, S.; Bui, Q.B.A.; Truß, A., Going weighted: parameterized algorithms for cluster editing, (), 1-12 · Zbl 1168.68441
[7] Böcker, S.; Briesemeister, S.; Klau, G.W., Exact algorithms for cluster editing: evaluation and experiments, (), 289-302 · Zbl 1215.68168
[8] Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony, Clustering with qualitative information, Journal of computer and system sciences, 71, 3, 360-383, (2005) · Zbl 1094.68075
[9] Chen, J.; Fernau, Henning; Kanj, Iyad A.; Xia, Ge, Parametric duality and kernelization: lower bounds and upper bounds on kernel size, SIAM journal on computing, 37, 4, 1077-1106, (2007) · Zbl 1141.05075
[10] Chen, Zhi-Zhong; Jiang, Tao; Lin, Guohui, Computing phylogenetic roots with bounded degrees and errors, SIAM journal on computing, 32, 4, 864-879, (2003) · Zbl 1053.68069
[11] Dehne, F.; Langston, M.A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y., The cluster editing problem: implementations and experiments, (), 13-24 · Zbl 1154.68451
[12] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R., Extending the tractability border for closest leaf powers, (), 397-408, Long version unter the title “Closest 4-leaf power is fixed-parameter tractable” to appear in Discrete Applied Mathematics · Zbl 1171.68496
[13] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R., Error compensation in leaf power problems, Algorithmica, 44, 4, 363-381, (2006) · Zbl 1095.68080
[14] Downey, Rodney G.; Fellows, Michael R., Parameterized complexity, (1999), Springer · Zbl 0961.68533
[15] Fellows, Michael R., The lost continent of polynomial time: preprocessing and kernelization, (), 312-321 · Zbl 1154.68560
[16] Fellows, M.R.; Langston, Michael A.; Rosamond, Frances; Shaw, Peter, Polynomial-time linear kernelization for cluster editing, (), 276-277
[17] Flum, Jörg; Grohe, Martin, Parameterized complexity theory, (2006), Springer · Zbl 1143.68016
[18] Giotis, I.; Guruswami, V., Correlation clustering with a fixed number of clusters, (), 1167-1176 · Zbl 1194.62087
[19] Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Graph-modeled data clustering: exact algorithms for clique generation, Theory of computing systems, 38, 4, 373-392, (2005) · Zbl 1084.68117
[20] Guo, J., A more effective linear kernelization for cluster editing, (), 36-47 · Zbl 1176.05078
[21] Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, ACM SIGACT news, 38, 1, 31-45, (2007)
[22] Hsu, W.; Ma, T., Substitution decomposition on chordal graphs and applications, (), 52-60
[23] Křivánek, Mirko; Morávek, Jaroslav, NP-hard problems in hierarchical-tree clustering, Acta informatica, 23, 3, 311-323, (1986) · Zbl 0644.68055
[24] Lin, Guohui; Kearney, Paul E.; Jiang, Tao, Phylogenetic \(k\)-root and Steiner \(k\)-root, (), 539-551 · Zbl 1044.68704
[25] Niedermeier, Rolf, Invitation to fixed-parameter algorithms, (2006), Oxford University Press · Zbl 1095.68038
[26] Protti, F.; da Silva, M.D.; Szwarcfiter, J.L., Applying modular decomposition to parameterized bicluster editing, (), 1-12, Long version to appear in Theory of Computing Systems · Zbl 1154.68455
[27] Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete applied mathematics, 144, 173-182, (2004) · Zbl 1068.68107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.