"Kernelizations for Chordal Completion

Completion in the framework of parameterized complexity. Chordal
Completion is also known as Minimum Fill-In. The task of Chordal
Completion is, given a graph G and an integer k, to decide whether G
can be transformed into a chordal graph by adding at most k edges. It
has been shown by Kaplan et al. that Chordal Completion is
fixed-parameter tractable with respect to the parameter k.

We present two kernelizations for Chordal Completion. The first
problem kernel has O(k^2) vertices, which is a known result by
Natanzon et al., but we use a simplified approach by means of two data
reduction rules. We improve this kernel by using a third reduction
rule and obtain a kernel with O(k^2) vertices and O(k^3) edges.