Parameterized algorithms for Max Colorable induced subgraph problem on perfect graphs

Abstract

We address the parameterized complexity of Max Colorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril (Inf Process Lett 24:133–137, 1987) showed that this problem is NP-complete even on split graphs if q is part of input, but gave an nO(q) algorithm on chordal graphs. We first observe that the problem is W[2]-hard when parameterized by q, even on split graphs. However, when parameterized by ℓ , the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44ℓ(n+t)O(1) where t is the number of maximal independent sets of the input graph.

The second algorithm runs in time O(6.75ℓ+o(ℓ)nO(1)) on graph classes where the maximum independent set of an induced subgraph can be found in polynomial time.

The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. Finally, we show that (under standard complexity-theoretic assumption) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input.

(b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q≥2 .