Cluster editing: kernelization based on edge cuts. (English) Zbl 1253.68144
Summary: Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Most kernelization algorithms for the problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present a simple algorithm that constructs a \(2k\)-vertex kernel for the integral-weighted version of the cluster editing problem. Our result matches the best kernel bound for the unweighted version of the cluster editing problem, and significantly improves the previous best kernel bound for the weighted version of the problem. For the more general real-weighted version of the problem, our techniques lead to a simple kernelization algorithm that constructs a kernel of at most \(4k\) vertices.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C22 | Signed and weighted graphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 1–27 (2008). Article 23 · doi:10.1145/1411509.1411513 |
| [2] | Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: ICALP 2009. LNCS, vol. 5555, pp. 49–58. Springer, Berlin (2009) · Zbl 1248.68547 |
| [3] | Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1), 89–113 (2004) · Zbl 1089.68085 · doi:10.1023/B:MACH.0000033116.57574.95 |
| [4] | Berkhin, P.: A survey of clustering data mining techniques. In: Grouping Multidimensional Data, pp. 25–71. Springer, Berlin (2006) |
| [5] | Betzler, N., Guo, J., Komusiewicz, C., Niedermeier, R.: Average parameterization and partial kernelization for computing medians. J. Comput. Syst. Sci. 77(4), 774–789 (2011) · Zbl 1215.68107 · doi:10.1016/j.jcss.2010.07.005 |
| [6] | Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. (2010). doi: 10.1016/j.jcss.2010.10.001 · Zbl 1235.05134 |
| [7] | Böcker, S., Briesemeister, S., Bui, Q.B.A., Truss, A.: Going weighted: parameterized algorithms for cluster editing. Theor. Comput. Sci. 410, 5467–5480 (2009) · Zbl 1178.68373 · doi:10.1016/j.tcs.2009.05.006 |
| [8] | Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360–383 (2005) · Zbl 1094.68075 · doi:10.1016/j.jcss.2004.10.012 |
| [9] | Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. J. Comput. Syst. Sci. (2011). doi: 10.1016/j.jcss.2011.04.001 · Zbl 1286.05164 |
| [10] | Cunningham, W.H., Edmonds, J.: A combinatorial decomposition theory. Can. J. Math. 32(3), 734–765 (1980) · Zbl 0442.05054 · doi:10.4153/CJM-1980-057-7 |
| [11] | Dean, J., Henzinger, M.R.: Finding related pages in the World Wide Web. Comput. Netw. 31, 1467–1479 (1999) · doi:10.1016/S1389-1286(99)00022-5 |
| [12] | Feige, U.: Faster FAST. In: CoRR (2009). arXiv:0911.5094 |
| [13] | Fellows, M.R., Langston, M.A., Rosamond, F.A., Shaw, P.: Efficient parameterized preprocessing for cluster editing. In: FCT 2007. LNCS, vol. 4639, pp. 312–321. Springer, Berlin (2007) · Zbl 1135.68511 |
| [14] | Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373–392 (2005) · Zbl 1084.68117 · doi:10.1007/s00224-004-1178-y |
| [15] | Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8–10), 718–726 (2009) · Zbl 1162.68025 · doi:10.1016/j.tcs.2008.10.021 |
| [16] | Hearst, M.A., Pedersen, J.O.: Reexamining the cluster hypothesis: scatter/gather on retrieval results. In: Proceedings of SIGIR, pp. 76–84 (1996) |
| [17] | Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: ISAAC 2010. LNCS, vol. 6506, pp. 3–14. Springer, Berlin (2010) · Zbl 1310.68272 |
| [18] | Komusiewicz, C.: Algorithmics for network analysis: Clustering & querying. PhD thesis, Technische Universität Berlin, Berlin, Germany (2011) |
| [19] | Krivánek, M., Morávek, J.: NP-hard problems in hierarchical-tree clustering. Acta Inform. 23(3), 311–323 (1986) · Zbl 0644.68055 · doi:10.1007/BF00289116 |
| [20] | de Montgolfier, F.: Décomposition modulaire des graphes. Théorie, extensions et algorithmes. Thése de doctorat, Université Montpellier II (2003) |
| [21] | Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1–2), 173–182 (2004) · Zbl 1068.68107 · doi:10.1016/j.dam.2004.01.007 |
| [22] | van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res. 34(3), 594–620 (2009) · Zbl 1216.68343 · doi:10.1287/moor.1090.0385 |
| [23] | Wittkop, T., Baumbach, J., Lobo, F., Rahmann, S.: Large scale clustering of protein sequences with FORCE–A layout based heuristic for weighted cluster editing. BMC Bioinform. 8(1), 396 (2007) · doi:10.1186/1471-2105-8-396 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
