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
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
EISSN: 1432-0541
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

SCOPUSTM   
Citations

5
Last Week
0
Last month
0
Citations as of Aug 18, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Aug 14, 2017

Page view(s)

43
Last Week
4
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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