Chordal Editing is Fixed-Parameter Tractable

Graph modification problems typically ask for 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 that allows all three types of operations: given a graph [InlineEquation not available: see fulltext.] and integers [InlineEquation not available: see fulltext.], and [InlineEquation not available: see fulltext.], the chordal editing problem asks whether [InlineEquation not available: see fulltext.] can be transformed into a chordal graph by at most [InlineEquation not available: see fulltext.] vertex deletions, [InlineEquation not available: see fulltext.] edge deletions, and [InlineEquation not available: see fulltext.] edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time [InlineEquation not available: see fulltext.], where [InlineEquation not available: see fulltext.] and [InlineEquation not available: see fulltext.] is the number of vertices of [InlineEquation not available: see fulltext.]. 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.