Even faster parameterized cluster deletion and cluster editing. (English) Zbl 1260.05156
Summary: Cluster Deletion and Cluster Editing ask to transform a graph by at most \(k\) edge deletions or edge edits, respectively, into a cluster graph, i.e., disjoint union of cliques. Equivalently, a cluster graph has no conflict triples, i.e., two incident edges without a transitive edge. We solve the two problems in time \(O^{\ast}(k^{1.415})\) and \(O^{\ast}(k^{1.76})\), respectively. These results round off our earlier work by considerably improved time bounds. For Cluster Deletion we use a technique that cuts away small connected components that do no longer contribute to the exponential part of the time complexity. As this idea is simple and versatile, it may lead to improvements for several other parameterized graph problems. The improvement for Cluster Editing is achieved by using the full power of an earlier structure theorem for graphs where no edge is in three conflict triples.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
graph algorithms; cluster deletion; cluster editing; parameterized complexity; graph transformation; edge deletion; eddge editingReferences:
| [1] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [2] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms, Oxford Lecture Ser. Math. Appl. (2006), Oxford Univ. Press · Zbl 1095.68038 |
| [3] | Dehne, F.; Langston, M. A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y., The cluster editing problem: implementations and experiments, (Bodlaender, H. L.; Langston, M. A., Int. Workshop on Parameterized and Exact Comp., IWPEC 2006. Int. Workshop on Parameterized and Exact Comp., IWPEC 2006, LNCS, vol. 4169 (2006), Springer: Springer Heidelberg), 13-24 · Zbl 1154.68451 |
| [4] | Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Graph-modeled data clustering: Fixed-parameter algorithms for clique generation, Theory Comput. Syst., 38, 373-392 (2005) · Zbl 1084.68117 |
| [5] | Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Appl. Math., 144, 173-182 (2004) · Zbl 1068.68107 |
| [6] | Wittkop, T.; Emig, D.; Lange, S.; Rahmann, S.; Albrecht, M.; Morris, J. H.; Böcker, S.; Stoye, J.; Baumbach, J., Partitioning biological data with transitivity clustering, Nat. Methods, 7, 419-420 (2010) |
| [7] | Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 196-217 (2010) · Zbl 1205.68263 |
| [8] | Damaschke, P., Fixed-parameter enumerability of cluster editing and related problems, Theory Comput. Syst., 46, 261-283 (2010) · Zbl 1209.68360 |
| [9] | Böcker, S.; Briesemeister, S.; Bui, Q. B.A.; Truss, A., Going weighted: Parameterized algorithms for cluster editing, Theoret. Comput. Sci., 410, 5467-5480 (2009) · Zbl 1178.68373 |
| [10] | Guo, J., A more effective linear kernelization for cluster editing, Theoret. Comput. Sci., 410, 718-726 (2009) · Zbl 1162.68025 |
| [11] | Chen, J.; Meng, J., A \(2k\) kernel for the cluster editing problem, (Thai, M. T.; Sahni, S., Computing and Combinatorics Conf., COCOON 2010. Computing and Combinatorics Conf., COCOON 2010, LNCS, vol. 6196 (2010), Springer: Springer Heidelberg), 459-468 · Zbl 1286.05164 |
| [12] | Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Automated generation of search tree algorithms for hard graph modification problems, Algorithmica, 39, 321-347 (2004) · Zbl 1090.68027 |
| [13] | Damaschke, P., Bounded-degree techniques accelerate some parameterized graph algorithms, (Chen, J.; Fomin, F. V., Int. Workshop on Parameterized and Exact Comp., IWPEC 2009. Int. Workshop on Parameterized and Exact Comp., IWPEC 2009, LNCS, vol. 5917 (2009), Springer: Springer Heidelberg), 98-109 · Zbl 1273.68426 |
| [14] | Mannaa, B., Cluster editing problem for points on the real line: A polynomial time algorithm, Inform. Process. Lett., 110, 961-965 (2010) · Zbl 1379.68258 |
| [15] | Goldberg, A. V.; Rao, S., Beyond the flow decomposition barrier, J. ACM, 45, 783-797 (1998) · Zbl 1064.90567 |
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.
