[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


@inproceedings {
title="{Contraction Blockers for Graphs with Forbidden Induced Paths}",
author=" C. Picouleau and B. Ries and D. Paulusma and O. Diner ",
booktitle="{CIAC 2015}",
address="Paris, France",