Document Open Access Logo

Cluster Deletion on Interval Graphs and Split Related Graphs

Authors Athanasios L. Konstantinidis, Charis Papadopoulos

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.12.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Athanasios L. Konstantinidis
  • Department of Mathematics, University of Ioannina, Greece
Charis Papadopoulos
  • Department of Mathematics, University of Ioannina, Greece

Funding

This research is co-financed by Greece and the European Union (European Social Fund - ESF) through the Operational Programme "Human Resources Development, Education and Lifelong Learning" in the context of the project "Strengthening Human Resources Research Potential via Doctorate Research" (MIS-5000432), implemented by the State Scholarships Foundation (IKY).

Cite AsGet BibTex

Athanasios L. Konstantinidis and Charis Papadopoulos. Cluster Deletion on Interval Graphs and Split Related Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.12

Abstract

In the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Cluster deletion
  • interval graphs
  • split graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56:89-113, 2004. Google Scholar
  2. 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 P₄-sparse graphs. Inf. Proc. Lett., 115:600-603, 2015. Google Scholar
  3. F. Bonomo, G. Durán, and M. Valencia-Pabon. Complexity of the cluster deletion problem on subclasses of chordal graphs. Theor. Comp. Science, 600:59-69, 2015. Google Scholar
  4. B. Bui-Xuan, J. A. Telle, and M. Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. Google Scholar
  5. M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. In Proceedings of FOCS 2003, pages 524-533, 2003. Google Scholar
  6. B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12-75, 1990. Google Scholar
  7. A. Dessmark, J. Jansson, A. Lingas, E.-M. Lundell, and M. Persson. On the approximability of maximum and minimum edge clique partition problems. Int. J. Found. Comput. Sci., 18:217-226, 2007. Google Scholar
  8. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2012. Google Scholar
  9. S. Földes and P. L. Hammer. Split graphs. Congressus Numerantium, 19:311-315, 1977. Google Scholar
  10. D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15:835-855, 1965. Google Scholar
  11. Y. Gao, D. R. Hare, and J. Nastos. The cluster deletion problem for cographs. Discrete Mathematics, 313:2763-2771, 2013. Google Scholar
  12. M. U. Gerber and D. Kobler. Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theor. Comp. Science, 299:719-734, 2003. Google Scholar
  13. P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. Google Scholar
  14. P. A. Golovach, P. Heggernes, A. L. Konstantinidis, P. T. Lima, and C. Papadopoulos. Parameterized aspects of strong subgraph closure. In Proceedings of SWAT 2018, pages 23:1-23:13, 2018. Google Scholar
  15. M. C. Golumbic and U. Rotics. On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci., 11:423-443, 2000. Google Scholar
  16. N. Grüttemeier and C. Komusiewicz. On the relation of strong triadic closure and cluster deletion. In Proceedings of WG 2018, pages 239-251, 2018. Google Scholar
  17. P. L. Hammer and B. Simeone. The splittance of a graph. Combinatorica, 1:275-284, 1981. Google Scholar
  18. P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Math. Programming, 79:191-215, 1997. Google Scholar
  19. J. Hartigan. Clustering Algorithms. Wiley, New York, 1975. Google Scholar
  20. P. Heggernes, D. Lokshtanov, J. Nederlof, C. Paul, and J. A. Telle. Generalized graph clustering: recognizing (p,q)-cluster graphs. In Proceedings of WG 2010, pages 171-183, 2010. Google Scholar
  21. I. A. Kanj, C. Komusiewicz, M. Sorge, and E. Jan van Leeuwen. Solving partition problems almost always requires pushing many vertices around. In Proceedings of ESA 2018, pages 51:1-51:14, 2018. Google Scholar
  22. C. Komusiewicz and J. Uhlmann. Cluster editing with locally bounded modifications. Discrete Applied Mathematics, 160:2259-2270, 2012. Google Scholar
  23. S. E. Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. Google Scholar
  24. R. Shamir, R. Sharan, and D. Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144:173-182, 2004. Google Scholar
  25. J. A. Telle and A. Proskurowski. Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM J. Discrete Math., 10:529-550, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact