# A new polynomial class of cluster deletion problem

## Sabrine Malek, Wady Naanaa

DOI: http://dx.doi.org/10.15439/2016F273

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 585–590 (2016)

Abstract. Cluster Deletion (CD) problem asks to transform a given graph into a cluster graph by at most k edge deletions. CD is a combinatorial problem arising in the field of classification. In this paper, we introduce a graph transformation which enabled the identification of new polynomially solvable classes of CD problem. We show that if a graph is K3-free or (diamond, kite, house, xbanner)-free then cluster deletion problem can be solved in polynomial time on that graph.

### References

- M. Azad and M. Moshkov, “Classification and optimization of decision trees for inconsistent decision tables represented as MVD tables,” in 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Łódz, Poland, September 13-16, 2015, 2015, pp. 31–38. [Online]. Available: http://dx.doi.org/10.15439/2015F231
- R. Ziembinski, “Unsupervised extraction of graph-stream structure for purpose of knowledge retrieval and information fusion,” in Position Papers of the 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lódz, Poland, September 13-16, 2015., 2015, pp. 53–60. [Online]. Available: http://dx.doi.org/10.15439/2015F288
- C.-T. Cheng, C. K. Tse, and F. C. M. Lau, “A clustering algorithm for wireless sensor networks based on social insect colonies,” IEEE Sensors Journal, pp. 711–721, 2010. [Online]. Available: http://dx.doi.org/10.1109/JSEN.2010.2063021
- C. S. Nam, Y. S. Han, and D. R. Shin, “Multi-hop routing-based optimization of the number of cluster-heads in wireless sensor networks,” Sensors Journal, pp. 2875–2884, 2011. [Online]. Available: http://dx.doi.org/10.3390/s110302875
- N. Amini, A. Vahdatpour, W. Xu, M. Gerla, and M. Sarrafzadeh, “Cluster size optimization in sensor networks with decentralized clusterbased protocols.” Computer Communications, pp. 207–220, 2012. [Online]. Available: http://dx.doi.org/10.1016/j.comcom.2011.09.009
- J. Cong and S. K. Lim, “Edge separability-based circuit clustering with application to multilevel circuit partitioning,” IEEE Trans. on CAD of Integrated Circuits and Systems, pp. 346–357, 2004. [Online]. Available: http://dx.doi.org/10.1109/TCAD.2004.823353
- R. Shamir, R. Sharan, and D. Tsur, “Cluster graph modification problems,” Discrete Applied Mathematics, pp. 173–182, 2004. [Online]. Available: http://dx.doi.org/10.1016/j.dam.2004.01.007
- F. Bonomo, G. Durán, and M. Valencia-Pabon, “Complexity of the cluster deletion problem on subclasses of chordal graphs,” Theor. Comput. Sci., pp. 59–69, 2015. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2015.07.001
- Y. Gao, D. R. Hare, and J. Nastos, “The cluster deletion problem for cographs,” Discrete Mathematics, pp. 2763–2771, 2013. [Online]. Available: http://dx.doi.org/10.1016/j.disc.2013.08.017
- F. Bonomo, G. Durán, A. Napoli, and M. Valencia-Pabon, “A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4 -sparse graphs,” Inf. Process. Lett., pp. 600–603, 2015. [Online]. Available: http://dx.doi.org/10.1016/j.ipl.2015.02.007
- J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices,” Journal of Research of the National Bureau of Standards B, pp. 125–130, 1965. [Online]. Available: http://archive.org/details/jresv69Bn1-2p125
- V. V. Lozin and M. Milanic, “A polynomial algorithm to find an independent set of maximum weight in a fork-free graph,” J. Discrete Algorithms, pp. 595–604, 2008. [Online]. Available: http://dx.doi.org/10.1016/j.jda.2008.04.001
- J. Edmonds, “Paths, trees, and flowers,” Canad. J. Math., pp. 449–467, 1965. [Online]. Available: http://dx.doi.org/10.4153/CJM-1965-045-4
- C. Berge, “Two theorems in graph theory,” Proceedings of the National Academy of Sciences of the United States of America, pp. 842–844, 1957. [Online]. Available: http://www.jstor.org/stable/89875
- V. V. Lozin, “Conic reduction of graphs for the stable set problem,” Discrete Mathematics, pp. 199–211, 2000. [Online]. Available: http://dx.doi.org/10.1016/S0012-365X(99)00408-2
- A. Brandstädt and P. L. Hammer, “On the stability number of claw-free P5-free and more general graphs,” Discrete Applied Mathematics, pp. 163–167, 1999. [Online]. Available: http://dx.doi.org/10.1016/S0166-218X(99)00072-4
- L. Lovàsz and M. D. Plummer, Matching theory. Amsterdam, New York: North-Holland, 1986. [Online]. Available: http://opac.inria.fr/record=b1086098
- P. A. Catlin, “A reduction method for graphs,” in Proc. 19th Southeastern Conf. (Baton Rouge), Congressus Numerantium 65, 1988, pp. 159–170.
- A. Goldman and Y. Ngoko, “On graph reduction for qos prediction of very large web service compositions,” in IEEE Ninth International Conference on Services Computing, Honolulu, HI, USA, 2012, pp. 258–265. [Online]. Available: http://dx.doi.org/10.1109/SCC.2012.21
- J. Cardoso, A. P. Sheth, J. A. Miller, J. Arnold, and K. Kochut, “Quality of service for workflows and web service processes,” J. Web Sem., pp. 281–308, 2004. [Online]. Available: http://dx.doi.org/10.1016/j.websem.2004.03.001
- H. N. de Ridder et al., “Information System on Graph Classes and their Inclusions (ISGCI),” http://www.graphclasses.org.