Chordal deletion is fixed-parameter tractable

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices. Here we present a uniformly polynomial-time algorithm for the problem: the running time is f(k) (.) n(alpha) for some constant a not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the 0(n(k)) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices to be deleted is fixed-parameter tractable. This answers an open question of Cai [2].