Complexity of the cluster deletion problem on some subclasses of chordal graphs
Identifieur interne : 000810 ( Main/Exploration ); précédent : 000809; suivant : 000811Complexity of the cluster deletion problem on some subclasses of chordal graphs
Auteurs : Flavia Bonomo [Argentine] ; Guillermo Duran [Argentine] ; Mario Valencia-Pabon [France]Source :
English descriptors
- mix :
Abstract
We consider the following vertex-partition problem on graphs: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case cliques) to minimize the total weight of edges out of the clusters. This optimization problem is known to be an NP-complete problem even for unweighted graphs and has been studied extensively in the scope of fixed-parameter tractability (FPT), where it is commonly known as the CLUSTER DELETION problem. Many of the recently-developed FPT algorithms rely on being able to solve CLUSTER DELETION in polynomial-time on restricted graph structures. In this paper, the complexity of the CLUSTER DELETION problem is investigated for the family of chordal graphs. It is shown that this problem is NP-complete for edge-weighted split graphs, edge-weighted interval graphs and edge-unweighted chordal graphs. We also prove that the CLUSTER DELETION is an NP-complete problem for edge-weighted cographs. Some polynomial-time solvable cases are also identified, in particular CLUSTER DELETION for unweighted split graphs, unweighted proper interval graphs and weighted block graphs.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001704
- to stream Hal, to step Curation: 001704
- to stream Hal, to step Checkpoint: 000725
- to stream Main, to step Merge: 000808
- to stream Main, to step Curation: 000810
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Complexity of the cluster deletion problem on some subclasses of chordal graphs</title><author><name sortKey="Bonomo, Flavia" sort="Bonomo, Flavia" uniqKey="Bonomo F" first="Flavia" last="Bonomo">Flavia Bonomo</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-92878" status="VALID"><orgName>Consejo Nacional de Investigaciones Científicas y Técnicas</orgName><orgName type="acronym">CONICET</orgName><desc><address><addrLine>Avda. Rivadavia 1917 - CP C1033AAJ - Cdad. de Buenos Aires</addrLine><country key="AR"></country></address><ref type="url">http://www.conicet.gov.ar/</ref></desc><listRelation><relation active="#struct-305291" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-305291" type="direct"><org type="institution" xml:id="struct-305291" status="INCOMING"><orgName>University of Buenos Aires</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Argentine</country></affiliation></author><author><name sortKey="Duran, Guillermo" sort="Duran, Guillermo" uniqKey="Duran G" first="Guillermo" last="Duran">Guillermo Duran</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-92878" status="VALID"><orgName>Consejo Nacional de Investigaciones Científicas y Técnicas</orgName><orgName type="acronym">CONICET</orgName><desc><address><addrLine>Avda. Rivadavia 1917 - CP C1033AAJ - Cdad. de Buenos Aires</addrLine><country key="AR"></country></address><ref type="url">http://www.conicet.gov.ar/</ref></desc><listRelation><relation active="#struct-305291" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-305291" type="direct"><org type="institution" xml:id="struct-305291" status="INCOMING"><orgName>University of Buenos Aires</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Argentine</country></affiliation></author><author><name sortKey="Valencia Pabon, Mario" sort="Valencia Pabon, Mario" uniqKey="Valencia Pabon M" first="Mario" last="Valencia-Pabon">Mario Valencia-Pabon</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-994" status="VALID"><orgName>Laboratoire d'Informatique de Paris-Nord</orgName><orgName type="acronym">LIPN</orgName><desc><address><addrLine>Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse</addrLine><country key="FR"></country></address><ref type="url">http://www-lipn.univ-paris13.fr/</ref></desc><listRelation><relation active="#struct-303141" type="direct"></relation><relation active="#struct-303171" type="direct"></relation><relation active="#struct-305778" type="direct"></relation><relation name="UMR7030" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-303141" type="direct"><org type="institution" xml:id="struct-303141" status="VALID"><orgName>Université Paris 13</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-303171" type="direct"><org type="institution" xml:id="struct-303171" status="VALID"><orgName>Université Sorbonne Paris Cité (USPC)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-305778" type="direct"><org type="institution" xml:id="struct-305778" status="INCOMING"><orgName>Institut Galilée</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR7030" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Paris</settlement><region type="region" nuts="2">Île-de-France</region></placeName><orgName type="university">Université Paris 13</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01102512</idno><idno type="halId">hal-01102512</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01102512</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01102512</idno><date when="2015">2015</date><idno type="wicri:Area/Hal/Corpus">001704</idno><idno type="wicri:Area/Hal/Curation">001704</idno><idno type="wicri:Area/Hal/Checkpoint">000725</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000725</idno><idno type="wicri:Area/Main/Merge">000808</idno><idno type="wicri:Area/Main/Curation">000810</idno><idno type="wicri:Area/Main/Exploration">000810</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Complexity of the cluster deletion problem on some subclasses of chordal graphs</title><author><name sortKey="Bonomo, Flavia" sort="Bonomo, Flavia" uniqKey="Bonomo F" first="Flavia" last="Bonomo">Flavia Bonomo</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-92878" status="VALID"><orgName>Consejo Nacional de Investigaciones Científicas y Técnicas</orgName><orgName type="acronym">CONICET</orgName><desc><address><addrLine>Avda. Rivadavia 1917 - CP C1033AAJ - Cdad. de Buenos Aires</addrLine><country key="AR"></country></address><ref type="url">http://www.conicet.gov.ar/</ref></desc><listRelation><relation active="#struct-305291" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-305291" type="direct"><org type="institution" xml:id="struct-305291" status="INCOMING"><orgName>University of Buenos Aires</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Argentine</country></affiliation></author><author><name sortKey="Duran, Guillermo" sort="Duran, Guillermo" uniqKey="Duran G" first="Guillermo" last="Duran">Guillermo Duran</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-92878" status="VALID"><orgName>Consejo Nacional de Investigaciones Científicas y Técnicas</orgName><orgName type="acronym">CONICET</orgName><desc><address><addrLine>Avda. Rivadavia 1917 - CP C1033AAJ - Cdad. de Buenos Aires</addrLine><country key="AR"></country></address><ref type="url">http://www.conicet.gov.ar/</ref></desc><listRelation><relation active="#struct-305291" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-305291" type="direct"><org type="institution" xml:id="struct-305291" status="INCOMING"><orgName>University of Buenos Aires</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Argentine</country></affiliation></author><author><name sortKey="Valencia Pabon, Mario" sort="Valencia Pabon, Mario" uniqKey="Valencia Pabon M" first="Mario" last="Valencia-Pabon">Mario Valencia-Pabon</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-994" status="VALID"><orgName>Laboratoire d'Informatique de Paris-Nord</orgName><orgName type="acronym">LIPN</orgName><desc><address><addrLine>Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse</addrLine><country key="FR"></country></address><ref type="url">http://www-lipn.univ-paris13.fr/</ref></desc><listRelation><relation active="#struct-303141" type="direct"></relation><relation active="#struct-303171" type="direct"></relation><relation active="#struct-305778" type="direct"></relation><relation name="UMR7030" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-303141" type="direct"><org type="institution" xml:id="struct-303141" status="VALID"><orgName>Université Paris 13</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-303171" type="direct"><org type="institution" xml:id="struct-303171" status="VALID"><orgName>Université Sorbonne Paris Cité (USPC)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-305778" type="direct"><org type="institution" xml:id="struct-305778" status="INCOMING"><orgName>Institut Galilée</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR7030" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Paris</settlement><region type="region" nuts="2">Île-de-France</region></placeName><orgName type="university">Université Paris 13</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Block graphs</term><term>Chordal graphs</term><term>Cliques</term><term>Cluster deletion</term><term>Cographs</term><term>Edge-deletion</term><term>Interval graphs</term><term>NP-completeness</term><term>Split graphs</term><term>Submodular functions</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We consider the following vertex-partition problem on graphs: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case cliques) to minimize the total weight of edges out of the clusters. This optimization problem is known to be an NP-complete problem even for unweighted graphs and has been studied extensively in the scope of fixed-parameter tractability (FPT), where it is commonly known as the CLUSTER DELETION problem. Many of the recently-developed FPT algorithms rely on being able to solve CLUSTER DELETION in polynomial-time on restricted graph structures. In this paper, the complexity of the CLUSTER DELETION problem is investigated for the family of chordal graphs. It is shown that this problem is NP-complete for edge-weighted split graphs, edge-weighted interval graphs and edge-unweighted chordal graphs. We also prove that the CLUSTER DELETION is an NP-complete problem for edge-weighted cographs. Some polynomial-time solvable cases are also identified, in particular CLUSTER DELETION for unweighted split graphs, unweighted proper interval graphs and weighted block graphs.</div></front></TEI><affiliations><list><country><li>Argentine</li><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>Paris</li></settlement><orgName><li>Université Paris 13</li></orgName></list><tree><country name="Argentine"><noRegion><name sortKey="Bonomo, Flavia" sort="Bonomo, Flavia" uniqKey="Bonomo F" first="Flavia" last="Bonomo">Flavia Bonomo</name></noRegion><name sortKey="Duran, Guillermo" sort="Duran, Guillermo" uniqKey="Duran G" first="Guillermo" last="Duran">Guillermo Duran</name></country><country name="France"><region name="Île-de-France"><name sortKey="Valencia Pabon, Mario" sort="Valencia Pabon, Mario" uniqKey="Valencia Pabon M" first="Mario" last="Valencia-Pabon">Mario Valencia-Pabon</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000810 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000810 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-01102512
|texte= Complexity of the cluster deletion problem on some subclasses of chordal graphs
}}
| This area was generated with Dilib version V0.6.33. |  |