Minimum fill-in and treewidth of image and image graphs Original Research Article

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 image and image graphs to be the graphs that can be made split by removing at most image edges and at most image vertices, respectively. We show that problems like treewidth and minimum fill-in are fixed parameter tractable with parameter image on image graphs. Along with positive results of fixed parameter tractability of several problems on image and image graphs, we also show a surprising hardness result. We prove that computing the minimum fill-in of image graphs is NP-hard even for image. This implies that also minimum fill-in of image graphs is NP-hard for every image. In contrast, we show that the treewidth of image 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.