Diner, Ö. and Paulusma, D. and Picouleau, C. and Ries, B. (2015) 'Contraction blockers for graphs with forbidden induced paths.', in Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings. , pp. 194-207. Lecture notes in computer science. (9079).
We 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-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-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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (307Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-319-18173-8_14|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18173-8_14.|
|Date accepted:||No date available|
|Date deposited:||20 January 2015|
|Date of first online publication:||May 2015|
|Date first made open access:||16 May 2016|
Save or Share this output
|Look up in GoogleScholar|