Abstract
Given a density measure Π, an undirected graph G and a nonnegative integer k, a Π-CLUSTER EDITING problem is to decide whether G can be modified into a graph where all connected components are Π-cliques, by at most k edge modifications. Previous studies have been conducted on the complexity and fixed-parameter tractability (FPT) of Π-CLUSTER EDITING based on several different density measures. However, whether these conclusions hold on bipartite graphs is yet to be examined. In this paper, we focus on three different density measures for bipartite graphs: (1) having at most s missing edges for each vertex (s-biplex), (2) having average degree at least |V| − s (average-s-biplex) and (3) having at most s missing edges within a single disjoint component (s-defective bicliques). First, the NP-completeness of the three problems is discussed and afterwards we show all these problems are fixed-parameter tractable with respect to the parameter (s,k).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N.: The multi-parameterized cluster editing problem. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 284–294. Springer, Heidelberg (2013)
Ailon, N., Avigdor-Elgrabli, N., Liberty, E.: An improved algorithm for bipartite correlation clustering. arXiv preprint arXiv:1012.3011 (2010)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning 56(1-3), 89–113 (2004)
Böcker, S., Briesemeister, S., Bui, Q.B.A., Truß, A.: Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science 410(52), 5467–5480 (2009)
Cao, Y., Chen, J.: Cluster editing: Kernelization based on edge cuts. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 60–71. Springer, Heidelberg (2010)
Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences 78(1), 211–220 (2012)
Cheng, Y., Church, G.M.: Biclustering of expression data. In: ISMB, vol. 8, pp. 93–103 (2000)
Fellows, M., Langston, M., Rosamond, F., Shaw, P.: Efficient parameterized preprocessing for cluster editing. In: Csuhaj-Varjú, E., Ésik, Z. (eds.) FCT 2007. LNCS, vol. 4639, pp. 312–321. Springer, Heidelberg (2007)
Fellows, M.R., Downey, R.G.: Parameterized complexity (1999)
Gonçalves, J.P., Madeira, S.C., Oliveira, A.L.: Biggests: Integrated environment for biclustering analysis of time series gene expression data. BMC Research Notes 2(1), 124 (2009)
Guo, J.: A more effective linear kernelization for cluster editing. Theoretical Computer Science 410(8), 718–726 (2009)
Guo, J., Hüffner, F., Komusiewicz, C., Zhang, Y.: Improved algorithms for bicluster editing. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 445–456. Springer, Heidelberg (2008)
Guo, J., Kanj, I.A., Komusiewicz, C., Uhlmann, J.: Editing graphs into disjoint unions of dense clusters. Algorithmica 61(4), 949–970 (2011)
Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: A more relaxed model for graph-based data clustering: S-plex cluster editing. SIAM Journal on Discrete Mathematics 24(4), 1662–1683 (2010)
Harpaz, R., Perez, H., Chase, H.S., Rabadan, R., Hripcsak, G., Friedman, C.: Biclustering of adverse drug events in the fda’s spontaneous reporting system. Clinical Pharmacology & Therapeutics 89(2), 243–250 (2010)
Niedermeier, R.: Invitation to fixed-parameter algorithms, vol. 3. Oxford University Press, Oxford (2006)
Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology 6(1), 139–154 (1978)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Applied Mathematics 144(1), 173–182 (2004)
Sun, P., Guo, J., Baumbach, J.: Integrated simultaneous analysis of different biomedical data types with exact weighted bi-cluster editing. Journal of Integrative Bioinformatics 9(2), 197 (2012)
van Zuylen, A.: Deterministic approximation algorithms for ranking and clustering problems. Technical Report 1431. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (2005)
Wittkop, T., Baumbach, J., Lobo, F.P., Rahmann, S.: Large scale clustering of protein sequences with force-a layout based heuristic for weighted cluster editing. BMC Bioinformatics 8(1), 396 (2007)
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. Nature Methods 7(6), 419–420 (2010)
Wittkop, T., Emig, D., Truss, A., Albrecht, M., Böcker, S., Baumbach, J.: Comprehensive cluster analysis with transitivity clustering. Nature Protocols 6(3), 285–295 (2011)
Yu, H., Paccanaro, A., Trifonov, V., Gerstein, M.: Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22(7), 823–829 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Sun, P., Guo, J., Baumbach, J. (2014). Complexity of Dense Bicluster Editing Problems. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds) Computing and Combinatorics. COCOON 2014. Lecture Notes in Computer Science, vol 8591. Springer, Cham. https://doi.org/10.1007/978-3-319-08783-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-08783-2_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08782-5
Online ISBN: 978-3-319-08783-2
eBook Packages: Computer ScienceComputer Science (R0)