Max q-Colorable Induced Subgraph on Perfect Graphs

We explore 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 (IPL 1987) showed that this problem is NP-complete even on split graphs (which is a proper subset of perfect graphs, chordal graphs and co-chordal graphs). However, they showed that for fixed q, the problem is solvable in time n^O(q) on chordal graphs. A natural question is whether the problem is fixed parameter tractable (FPT) when parameterized by the number of colors q, that is, whether the problem admits an algorithm with running time f(q)n^O(1). A simple reduction shows that the problem is W[2]-hard parameterized by q, even on split graphs. Thus, we study this problem with another natural parameter – the solution size – l.

We design two parameterized algorithms for the problem. The first one runs in time 5.44^l(n + #α(G))^O(1) where #α(G) is the number of maximal independent sets of the input graph and the second algorithm runs in time q^(l+o(l))n^O(1). Observe that since q < l for all non-trivial situations, we have that the second algorithm is FPT in l alone. 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 assumptions) the problem does not admit a polynomial kernel even on split graphs and on perfect graphs the problem does not admit a polynomial kernel even for fixed values of q > 1.