Chordal editing is fixed-parameter tractable

Graph modification problems are typically asked as follows: is there a set of κ operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the ame property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph G and integers κ1, κ2, and κ3, the chordal editing problem asks if G can be transformed into a chordal graph by at most κ1vertex deletions, κ2edge deletions, and κ3edge additions. Clearly, this problem generalizes both chordal vertex/edge deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time 2O(k log k)· nO(1), where κ := κ1+ κ2+ κ3; therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion.