Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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