Contraction blockers for graphs with forbidden induced paths

Diner, Ö; Paulusma, D.; Picouleau, C.; Ries, B.

Abstract

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[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.

Citation

Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2015, March). Contraction blockers for graphs with forbidden induced paths. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 9th International Conference on Algorithms and Complexity (CIAC 2015)
• Start Date: Mar 20, 2015
• End Date: Mar 22, 2015
• Publication Date: May 16, 2015
• Deposit Date: Dec 22, 2014
• Publicly Available Date: May 16, 2016
• Print ISSN: 0302-9743
• Pages: 194-207
• Series Title: Lecture notes in computer science
• Series Number: 9079
• Series ISSN: 0302-9743
• Book Title: Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings.
• ISBN: 9783319181721
• DOI: https://doi.org/10.1007/978-3-319-18173-8_14
• Public URL: https://durham-repository.worktribe.com/output/1152979