Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorPicouleau, Christophe*
dc.contributor.authorPaulusma, Daniël*
dc.contributor.authorDiner, Öznur*
dc.date.accessioned2016-06-28T08:37:19Z
dc.date.available2016-06-28T08:37:19Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15585
dc.descriptionCIAC 2015, Paris, France, May 20-22, 2015en
dc.language.isoenen
dc.subjectGraphsen
dc.subject.ddc005en
dc.titleContraction Blockers for Graphs with Forbidden Induced Pathsen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number, clique number and independence number. For each of these graph parameters we show that, when d is part of the input, this problem is polynomial-time solvable on P4-free graphs and NP-complete as well as W[1]-hard, with parameter d, for split graphs. As split graphs form a subclass of P5-free graphs, both results together give a complete complexity classification for Pℓ-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show, on the positive side, that the problem is polynomial-time solvable, for each parameter, on split graphs if d is fixed, i.e., not part of the input. We also initiate a study into other subclasses of perfect graphs, namely cobipartite graphs and interval graphs.en
dc.identifier.citationpages194-207en
dc.relation.ispartoftitleAlgorithms and Complexity; 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedingsen
dc.relation.ispartofeditorVangelis Th. Paschos, Peter Widmayer
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofdate2015
dc.relation.ispartofurl10.1007/978-3-319-18173-8en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-319-18172-1en
dc.relation.conftitleAlgorithms and Complexity; 9th International Conference, CIAC 2015en
dc.relation.confdate2015-05
dc.relation.confcityParisen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-18173-8_14en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-06-24T07:42:27Z
hal.person.labIds989*
hal.person.labIds16574*
hal.person.labIds74357*
hal.person.labIds147033*
hal.identifierhal-01338229*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record