Contraction Blockers for Graphs with Forbidden Induced Paths

dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorPaulusma, Daniel
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.date.accessioned2019-06-27T08:02:35Z
dc.date.available2019-06-27T08:02:35Z
dc.date.issued2015
dc.departmentFakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.description.abstractWe 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 P-4-free graphs and NP-complete as well as W[1]-hard with parameter d for split graphs. As split graphs form a subclass of P-5-free graphs both results together give a complete complexity classification for P-l-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_US]
dc.identifier.citation9
dc.identifier.doi10.1007/978-3-319-18173-8_14en_US
dc.identifier.endpage207
dc.identifier.isbn978-3-319-18173-8
dc.identifier.isbn978-3-319-18172-1
dc.identifier.issn0302-9743en_US
dc.identifier.issn1611-3349en_US
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.scopus2-s2.0-84944728432en_US
dc.identifier.scopusqualityQ2
dc.identifier.startpage194en_US
dc.identifier.urihttps://hdl.handle.net/20.500.12469/647
dc.identifier.urihttps://doi.org/10.1007/978-3-319-18173-8_14
dc.identifier.volume9079en_US
dc.identifier.wosWOS:000362016700015en_US
dc.identifier.wosqualityN/A
dc.institutionauthorDiner, Öznur Yaşaren_US
dc.language.isoenen_US
dc.publisherSpringer-Verlag Berlinen_US
dc.relation.journalAlgorithms and Complexity (CIAC 2015)en_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.titleContraction Blockers for Graphs with Forbidden Induced Pathsen_US
dc.typeConference Objecten_US
dspace.entity.typePublication

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Contraction Blockers for Graphs.pdf
Size:
405.27 KB
Format:
Adobe Portable Document Format
Description: