Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/20036
Title: Chordal Editing is Fixed-Parameter Tractable
Authors: Cao, Y 
Marx, D
Keywords: Chordal completion
Chordal deletion
Chordal graph
Clique tree decomposition
Graph modification problems
Holes
Parameterized computation
Simplicial vertex sets
Issue Date: 2015
Publisher: Springer New York LLC
Source: Algorithmica, 2015 How to cite?
Journal: Algorithmica 
Abstract: Graph modification problems typically ask for 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 that allows all three types of operations: given a graph [InlineEquation not available: see fulltext.] and integers [InlineEquation not available: see fulltext.], and [InlineEquation not available: see fulltext.], the chordal editing problem asks whether [InlineEquation not available: see fulltext.] can be transformed into a chordal graph by at most [InlineEquation not available: see fulltext.] vertex deletions, [InlineEquation not available: see fulltext.] edge deletions, and [InlineEquation not available: see fulltext.] edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time [InlineEquation not available: see fulltext.], where [InlineEquation not available: see fulltext.] and [InlineEquation not available: see fulltext.] is the number of vertices of [InlineEquation not available: see fulltext.]. 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.
URI: http://hdl.handle.net/10397/20036
ISSN: 0178-4617
DOI: 10.1007/s00453-015-0014-x
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

23
Last Week
0
Last month
Checked on Jan 15, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.