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 or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k) ·nα for some constant α not depending on k and some f depending only on k. For large values of n, such an algo-rithm is much better than trying all the O(nk) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai [4]