Minimum fill-in and treewidth of split+ke and split+kv graphs

In this paper we investigate how graph problems that are NP-hard in general, but polynomial time solvable on split graphs, behave on input graphs that are close to being split. For this purpose we define split+ke and split+kv graphs to be the graphs that can be made split by removing at most kk edges and at most kk vertices, respectively. We show that problems like treewidth and minimum fill-in are fixed parameter tractable with parameter kk on split+ke graphs. Along with positive results of fixed parameter tractability of several problems on split+ke and split+kv graphs, we also show a surprising hardness result. We prove that computing the minimum fill-in of split+kv graphs is NP-hard even for k=1k=1. This implies that also minimum fill-in of chordal+kv graphs is NP-hard for every kk. In contrast, we show that the treewidth of split+1v graphs can be computed in linear time. This gives probably the first graph class for which the treewidth and the minimum fill-in problems have different computational complexity.