An improved fixed-parameter algorithm for 2-club cluster edge deletion. (English) Zbl 1543.68260
Summary: A 2-club is a graph of diameter at most two. In the decision version of the 2-Club Cluster Edge Deletion problem, an undirected graph \(G\) is given along with an integer \(k\ge 0\) as parameter, and the question is whether \(G\) can be transformed into a disjoint union of 2-clubs by deleting at most \(k\) edges. A simple fixed-parameter algorithm solves the problem in \(\mathcal{O}^*(3^k)\), and a decade-old algorithm improved this running to \(\mathcal{O}^*(2.74^k)\) time via a more sophisticated case analysis. Unfortunately, this latter algorithm is shown to have a flawed branching scenario. A fixed-parameter algorithm that breaks the \(3^k\) barrier is presented in this paper, with a running time in \(\mathcal{O}^*(2.692^k)\). This also improves the previously claimed running time.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
Keywords:
correlation clustering; 2-club cluster edge deletion; cluster editing; fixed-parameter tractabilitySoftware:
solverALLReferences:
| [1] | Abu-Khzam, F. N., On the complexity of multi-parameterized cluster editing, J. Discret. Algorithms, 45, 26-34 (2017) · Zbl 1419.68056 |
| [2] | Abu-Khzam, F. N.; Egan, J.; Gaspers, S.; Shaw, A.; Shaw, P., Cluster editing with vertex splitting, (Lee, J.; Rinaldi, G.; Mahjoub, A. R., Combinatorial Optimization - 5th International Symposium. Combinatorial Optimization - 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018. Combinatorial Optimization - 5th International Symposium. Combinatorial Optimization - 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, Lecture Notes in Computer Science, vol. 10856 (2018), Springer), 1-13, (Revised Selected Papers) · Zbl 1403.90556 |
| [3] | Barr, J. R.; Shaw, P.; Abu-Khzam, F. N.; Chen, J., Combinatorial text classification: the effect of multi-parameterized correlation clustering, (2019 First International Conference on Graph Computing (GC) (2019)), 29-36 |
| [4] | Barr, J. R.; Shaw, P.; Abu-Khzam, F. N.; Thatcher, T.; Yu, S., Vulnerability rating of source code with token embedding and combinatorial algorithms, Int. J. Semant. Comput., 14, 04, 501-516 (2020) |
| [5] | Barr, J. R.; Shaw, P.; Abu-Khzam, F. N.; Yu, S.; Yin, H.; Thatcher, T., Combinatorial code classification & vulnerability rating, (2020 Second International Conference on Transdisciplinary AI (TransAI) (2020), IEEE), 80-83 |
| [6] | Böcker, S.; Baumbach, J., Cluster editing, (Bonizzoni, P.; Brattka, V.; Löwe, B., The Nature of Computation. Logic, Algorithms, Applications - Proceedings of the 9th Conference on Computability in Europe. The Nature of Computation. Logic, Algorithms, Applications - Proceedings of the 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. The Nature of Computation. Logic, Algorithms, Applications - Proceedings of the 9th Conference on Computability in Europe. The Nature of Computation. Logic, Algorithms, Applications - Proceedings of the 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013, Lecture Notes in Computer Science, vol. 7921 (2013), Springer), 33-44 · Zbl 1387.68177 |
| [7] | Böcker, S.; Briesemeister, S.; Klau, G. W., Exact algorithms for cluster editing: evaluation and experiments, Algorithmica, 60, 2, 316-334 (2011) · Zbl 1215.68169 |
| [8] | D’Addario, M.; Kopczynski, D.; Baumbach, J.; Rahmann, S., A modular computational framework for automated peak extraction from ion mobility spectra, BMC Bioinform., 15, 1 (2014) |
| [9] | Dehne, F.; Langston, M. A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y., The cluster editing problem: implementations and experiments, (Parameterized and Exact Computation (2006), Springer Berlin Heidelberg), 13-24 · Zbl 1154.68451 |
| [10] | Fadiel, A.; Langston, M. A.; Peng, X.; Perkins, A. D.; Taylor, H. S.; Tuncalp, O.; Vitello, D.; Pevsner, P. H.; Naftolin, F., Computational analysis of mass spectrometry data using novel combinatorial methods, (AICCSA, vol. 6 (2006)), 8-11 |
| [11] | Figiel, A.; Himmel, A.; Nichterlein, A.; Niedermeier, R., On 2-clubs in graph-based data clustering: theory and algorithm engineering, (Calamoneri, T.; Corò, F., Algorithms and Complexity - Proceedings of the 12th International Conference, CIAC 2021, Virtual Event. Algorithms and Complexity - Proceedings of the 12th International Conference, CIAC 2021, Virtual Event, May 10-12, 2021. Algorithms and Complexity - Proceedings of the 12th International Conference, CIAC 2021, Virtual Event. Algorithms and Complexity - Proceedings of the 12th International Conference, CIAC 2021, Virtual Event, May 10-12, 2021, Lecture Notes in Computer Science, vol. 12701 (2021), Springer), 216-230 · Zbl 07667132 |
| [12] | Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Graph-modeled data clustering: fixed-parameter algorithms for clique generation, (Petreschi, R.; Persiano, G.; Silvestri, R., Algorithms and Complexity, Proceedings of the 5th Italian Conference. Algorithms and Complexity, Proceedings of the 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003. Algorithms and Complexity, Proceedings of the 5th Italian Conference. Algorithms and Complexity, Proceedings of the 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Lecture Notes in Computer Science, vol. 2653 (2003), Springer), 108-119 · Zbl 1032.68158 |
| [13] | Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Automated generation of search tree algorithms for hard graph modification problems, Algorithmica, 39, 4, 321-347 (2004) · Zbl 1090.68027 |
| [14] | Guo, J., A more effective linear kernelization for cluster editing, Theor. Comput. Sci., 410, 8, 718-726 (2009) · Zbl 1162.68025 |
| [15] | Heggernes, P.; Lokshtanov, D.; Nederlof, J.; Paul, C.; Telle, J. A., Generalized graph clustering: recognizing (p, q)-cluster graphs, (Thilikos, D. M., Graph Theoretic Concepts in Computer Science - 36th International Workshop. Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010. Graph Theoretic Concepts in Computer Science - 36th International Workshop. Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010, Lecture Notes in Computer Science, vol. 6410 (2010)), 171-183, (Revised Papers) · Zbl 1309.68153 |
| [16] | Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 1, 196-217 (2010) · Zbl 1205.68263 |
| [17] | Komusiewicz, C.; Uhlmann, J., Cluster editing with locally bounded modifications, Discrete Appl. Math., 160, 15, 2259-2270 (2012) · Zbl 1252.05178 |
| [18] | Lee, V. E.; Ruan, N.; Jin, R.; Aggarwal, C. C., A survey of algorithms for dense subgraph discovery, (Aggarwal, C. C.; Wang, H., Managing and Mining Graph Data. Managing and Mining Graph Data, Advances in Database Systems, vol. 40 (2010), Springer), 303-336 · Zbl 1185.68458 |
| [19] | Liben-Nowell, D.; Kleinberg, J. M., The link-prediction problem for social networks, J. Assoc. Inf. Sci. Technol., 58, 7, 1019-1031 (2007) |
| [20] | Liu, H.; Zhang, P.; Zhu, D., On editing graphs into 2-club clusters, (Snoeyink, J.; Lu, P.; Su, K.; Wang, L., Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (2012), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 235-246 · Zbl 1304.68063 |
| [21] | Misra, N.; Panolan, F.; Saurabh, S., Subexponential algorithm for d-cluster edge deletion: exception or rule?, J. Comput. Syst. Sci., 113, 150-162 (2020) · Zbl 1445.68171 |
| [22] | Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Mathematics and Data Mining. Discrete Mathematics and Data Mining, Discrete Appl. Math., 144, 1, 173-182 (2004) · Zbl 1068.68107 |
| [23] | West, D. B., Introduction to Graph Theory (September 2000), Prentice Hall |
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.
