Ö Diner
Contraction blockers for graphs with forbidden induced paths
Diner, Ö; Paulusma, D.; Picouleau, C.; Ries, B.
Authors
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
Accepted Conference Proceeding
(314 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18173-8_14.
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search