Paper Info
Title
Minimum fill-in and treewidth of split+ke and split+kv graphs
Abstract
In this paper we investigate how graph problems that are NP-hard in general, but polynomially 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 k edges and at most k vertices, respectively. We show that problems like treewidth and minimum fill-in are fixed parameter tractable with parameter k 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 = 1. This implies that also minimum fill-in of chordal+kv graphs is NP-hard for every k. In contrast, we show that the treewidth of split+1v graphs can be computed in polynomial time. This gives probably the first graph class for which the treewidth and the minimum fill-in problems have different computational complexity.
Year
DOI
Venue
2007
10.1016/j.dam.2008.11.006
Discrete Applied Mathematics
Keywords
Field
DocType
parameterized algorithms,minimum fill-in,kv graph,parameter k,k vertex,treewidth,minimum fill-in problem,ke graph,fixed parameter tractability,k edge,split graphs,parameter tractable,split graph
Discrete mathematics,Combinatorics,Indifference graph,Partial k-tree,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics,Split graph
Conference
Volume
Issue
ISSN
158
7
Discrete Applied Mathematics
ISBN
Citations 
PageRank 
3-540-77118-2
3
0.39
References 
Authors
28
1
Name
Order
Citations
PageRank
Federico Mancini1789.79