Abstract:
We consider the following vertex-partition problem on graphs, known as the CLUSTER DELETION (CD) problem: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case, cliques) to minimize the total weight of edges outside the clusters. The decision version of this optimization problem is known to be NP-complete even for unweighted graphs and has been studied extensively. We investigate the complexity of the decision CD problem for the family of chordal graphs, showing that it is NP-complete for weighted split graphs, weighted interval graphs and unweighted chordal graphs. We also prove that the problem is NP-complete for weighted cographs. Some polynomial-time solvable cases of the optimization problem are also identified, in particular CD for unweighted split graphs, unweighted proper interval graphs and weighted block graphs. © 2015 Elsevier B.V.
Registro:
Documento: |
Artículo
|
Título: | Complexity of the cluster deletion problem on subclasses of chordal graphs |
Autor: | Bonomo, F.; Durán, G.; Valencia-Pabon, M. |
Filiación: | CONICET and Dep. de Computación, FCEN, Universidad de Buenos Aires, Argentina CONICET and Dep. de Matemática and Instituto de Cálculo, FCEN, Universidad de Buenos Aires, Argentina Dep. de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France
|
Palabras clave: | Block graphs; Chordal graphs; Cliques; Cluster deletion; Cographs; Edge-deletion; Interval graphs; NP-completeness; Split graphs; Submodular functions; Graphic methods; Optimization; Polynomial approximation; Polynomials; Block graphs; Chordal graphs; Cliques; Cluster deletion; Co-graphs; Edge-deletion; Interval graph; Np-completeness; Split graphs; Submodular functions; Graph theory |
Año: | 2015
|
Volumen: | 600
|
Página de inicio: | 59
|
Página de fin: | 69
|
DOI: |
http://dx.doi.org/10.1016/j.tcs.2015.07.001 |
Título revista: | Theoretical Computer Science
|
Título revista abreviado: | Theor Comput Sci
|
ISSN: | 03043975
|
CODEN: | TCSCD
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v600_n_p59_Bonomo |
Referencias:
- Bansal, N., Blum, A., Chawla, S., Correlation clustering (2004) Mach. Learn., 56 (1-3), pp. 89-113. , Extended abstract appeared in FOCS 2002, pp. 238-247
- Blair, J.R.S., Peyton, B., An introduction to chordal graphs and clique trees (1993) The IMA Volumes in Mathematics and Its Applications, 56, pp. 1-29. , Graph Theory and Sparse Matrix Computation
- Böcker, S., Damaschke, P., Even faster parametrized cluster deletion and cluster editing (2011) Inform. Process. Lett., 111, pp. 717-721
- Bonomo, F., Durán, G., Napoli, A., Valencia-Pabon, M., A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P<inf>4</inf>-sparse graphs (2015) Inform. Process. Lett., 115, pp. 600-603
- Charikar, M., Guruswami, V., Wirth, A., Clustering with qualitative information (2003) Proc. of 44th Annu. IEEE Symp. Foundations of Computer Science, pp. 524-533
- Damaschke, P., Mogren, O., Editing simple graphs (2014) J. Graph Algorithms Appl., 18 (4), pp. 557-576
- Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N., Correlation clustering in general weighted graphs (2006) Theoret. Comput. Sci., 361, pp. 172-187
- Dessmark, A., Lingas, A., Lundell, E.M., Persson, M., Jansson, J., On the approximability of maximum and minimum edge clique partitions problems (2007) Internat. J. Found. Comput. Sci., 18 (2), pp. 217-226
- Edmonds, J., Maximum matching and a polyhedron with 0, 1-vertices (1965) J. Res. Natl. Bur. Stand., B Math. Math. Phys., 69B, pp. 125-130
- Földes, S., Hammer, P.L., Split graphs (1977) Congressus Numerantium, 19, pp. 311-315. , Proc. of 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing
- Gao, Y., Hare, D.R., Nastos, J., The cluster deletion problem for cographs (2013) Discrete Math., 313, pp. 2763-2771
- Garey, M.R., Johnson, D.S., (1979) Computers and Intractability, , Freeman, San Francisco
- Hansen, P., Jaumard, B., Cluster analysis and mathematical programming (1997) Math. Program., 79, pp. 191-215
- Hartigan, J., (1975) Clustering Algorithms, , Wiley, New York
- Iwata, S., Fleischer, L., Fujishige, S., A combinatorial strongly polynomial algorithm for minimizing submodular functions (2001) J. ACM, 48, pp. 761-777
- Kaba, B., Pinet, N., Lelandais, G., Sigayret, A., Berry, A., Clustering gene expression data using graph separators (2007) In Silico Biol., 7 (4-5), pp. 433-452
- Komusiewicz, C., Uhlmann, J., Cluster editing with locally bounded modifications (2012) Discrete Appl. Math., 160 (15), pp. 2259-2270
- Kovac, I., Seleceniova, I., Steinova, M., On the clique editing problem (2014) LNCS, 8635, pp. 469-480. , Proc. of MFCS 2014
- Mannaa, B., Cluster editing problem for points on the real line: a polynomial time algorithm (2010) Inform. Process. Lett., 1610, pp. 961-965
- Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , Academic Press, F. Harary (Ed.)
- Schrijver, A., A combinatorial algorithm minimizing submodular functions in strongly polynomial time (2000) J. Combin. Theory Ser. B, 80, pp. 346-355
- Shamir, R., Sharan, R., Tsur, D., Cluster graph modification problems (2004) Discrete Appl. Math., 144 (1-2), pp. 173-182
- West, D.B., (2001) Introduction to Graph Theory, , Prentice-Hall
Citas:
---------- APA ----------
Bonomo, F., Durán, G. & Valencia-Pabon, M.
(2015)
. Complexity of the cluster deletion problem on subclasses of chordal graphs. Theoretical Computer Science, 600, 59-69.
http://dx.doi.org/10.1016/j.tcs.2015.07.001---------- CHICAGO ----------
Bonomo, F., Durán, G., Valencia-Pabon, M.
"Complexity of the cluster deletion problem on subclasses of chordal graphs"
. Theoretical Computer Science 600
(2015) : 59-69.
http://dx.doi.org/10.1016/j.tcs.2015.07.001---------- MLA ----------
Bonomo, F., Durán, G., Valencia-Pabon, M.
"Complexity of the cluster deletion problem on subclasses of chordal graphs"
. Theoretical Computer Science, vol. 600, 2015, pp. 59-69.
http://dx.doi.org/10.1016/j.tcs.2015.07.001---------- VANCOUVER ----------
Bonomo, F., Durán, G., Valencia-Pabon, M. Complexity of the cluster deletion problem on subclasses of chordal graphs. Theor Comput Sci. 2015;600:59-69.
http://dx.doi.org/10.1016/j.tcs.2015.07.001