|
 
|
[PRP15] Contraction Blockers for Graphs with Forbidden Induced Paths
Conférence Internationale avec comité de lecture : CIAC 2015, May 2015, Vol. LNCS(9079), pp.194-207, Paris, France,Mots clés: Graph, Blocker, Complexity, Algorithms
Résumé:
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 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.
Equipe:
oc
Collaboration:
LAMSADE
BibTeX
| @inproceedings { | |||
| PRP15, | |||
| title | = | "{Contraction Blockers for Graphs with Forbidden Induced Paths}", | |
| author | = | " C. Picouleau and B. Ries and D. Paulusma and O. Diner ", | |
| booktitle | = | "{CIAC 2015}", | |
| year | = | 2015, | |
| edition | = | "Springer", | |
| month | = | "May", | |
| volume | = | LNCS, | |
| issue | = | 9079, | |
| pages | = | "194-207", | |
| address | = | "Paris, France", | |
| } | |||
