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 $k_1$, $k_2$, and $k_3$, the $\text{textsc}chordalediting$ problem asks whether $G$ can be transformed into a chordal graph by at most $k_1$ vertex deletions, $k_2$ edge deletions, and $k_3$ edge additions. Clearly, this problem generalizes both $\text{textsc}chordalvertex\mathrm{/}edgedeletion$ and $\text{textsc}chordalcompletion$ (also known as $\text{textsc}minimumfill-in$). Our main result is an algorithm for $\text{textsc}chordalediting$ in time $2^{O(k\log k)}\cdot n^{O(1)}$,where$k:=k_1+k_2+k_3$and$n$isthenumberofverticesof$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 $\text{textsc}chordaldeletion$.