2014/05/30 by Cao, Yixin, Marx, Dániel · 1 citation
#05C75 #68R10 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1405.7859
Graph modification problems are typically asked as follows: is there a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph G and integers k1, k2, and k3, the chordal editing problem asks whether G can be transformed into a chordal graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge additions. Clearly, this problem generalizes both chordal vertex/edge deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time 2O(klog k)⋅ nO(1), where k:=k1+k2+k3 and n is the number of vertices of G. Therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion.