Skip to main content

Research Repository

Advanced Search

Contraction blockers for graphs with forbidden induced paths

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

Contraction blockers for graphs with forbidden induced paths Thumbnail


Authors

Ö Diner

C. Picouleau

B. Ries



Contributors

Vangelis Th Paschos
Editor

Peter Widmayer
Editor

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). Contraction blockers for graphs with forbidden induced paths. In V. T. Paschos, & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings (194-207). https://doi.org/10.1007/978-3-319-18173-8_14

Conference Name 9th International Conference on Algorithms and Complexity (CIAC 2015)
Conference Location Paris, France
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
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

Files





You might also like



Downloadable Citations