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 [IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a nO(q) algorithm on chordal graphs. We first observe that the problem is W-hard 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. 1. The first algorithm runs in time 5.44~ℓ(n + #α(G))~(O(1)) where #α(G) is the number of maximal independent sets of the input graph. 2. The second algorithm runs in time q~(ℓ+o(ℓ))n~(O(1))T_α where T_α is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in ℓ alone (whenever T_α is a polynomial in n), since q ≤ ℓ for all non-trivial situations. Finally, we show that (under standard complexity-theoretic assumptions) 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.
展开▼
