  We study the algorithmic properties of the graph class Chordal-ke, that is,
graphs that can be turned into a chordal graph by adding at most k edges or,
equivalently, the class of graphs of fill-in at most k. We discover that a
number of fundamental intractable optimization problems being parameterized by
k admit subexponential algorithms on graphs from Chordal-ke. We identify a
large class of optimization problems on Chordal-ke that admit algorithms with
the typical running time 2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}. Examples of the
problems from this class are finding an independent set of maximum weight,
finding a feedback vertex set or an odd cycle transversal of minimum weight, or
the problem of finding a maximum induced planar subgraph. On the other hand, we
show that for some fundamental optimization problems, like finding an optimal
graph coloring or finding a maximum clique, are FPT on Chordal-ke when
parameterized by k but do not admit subexponential in k algorithms unless ETH
fails. Besides subexponential time algorithms, the class of Chordal-ke graphs
appears to be appealing from the perspective of kernelization (with parameter
k). While it is possible to show that most of the weighted variants of
optimization problems do not admit polynomial in k kernels on Chordal-ke
graphs, this does not exclude the existence of Turing kernelization and
kernelization for unweighted graphs. In particular, we construct a polynomial
Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted)
Independent Set we design polynomial kernels on two interesting subclasses of
Chordal-ke, namely, Interval-ke and Split-ke graphs.
