Chordal Editing is Fixed-Parameter Tractable

Graph modification problems are typically asked as follows: is there a small 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 same 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 k1, k2, and k3, the chordal editing problem asks whether G can be transformed into a chordal graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge 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 2^{O(k log k)}·n^O(1), where k:=k1+k2+k3 and n is the number of vertices of G. 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.