License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.214
URN: urn:nbn:de:0030-drops-44591
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4459/
 Go to the corresponding LIPIcs Volume Portal

### Chordal Editing is Fixed-Parameter Tractable

 pdf-format:

### Abstract

Graph modification problems are typically asked as follows: is there a set of k 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 k_1, k_2, and k_3, the CHORDAL EDITING problem asks if G can be transformed into a chordal graph by at most k_1 vertex deletions, k_2 edge deletions, and k_3 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 2^O(k.log(k))·n^O(1), where k:=k_1+k_2+k_3; 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.

### BibTeX - Entry

```@InProceedings{cao_et_al:LIPIcs:2014:4459,
author =	{Yixin Cao and D{\'a}niel Marx},
title =	{{Chordal Editing is Fixed-Parameter Tractable}},
booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages =	{214--225},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-65-1},
ISSN =	{1868-8969},
year =	{2014},
volume =	{25},
editor =	{Ernst W. Mayr and Natacha Portier},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4459},
URN =		{urn:nbn:de:0030-drops-44591},
doi =		{10.4230/LIPIcs.STACS.2014.214},
annote =	{Keywords: chordal graph, parameterized computation, graph modification problems, chordal deletion, chordal completion, clique tree decomposition, holes, simplic}
}
```

 Keywords: chordal graph, parameterized computation, graph modification problems, chordal deletion, chordal completion, clique tree decomposition, holes, simplic Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) Issue Date: 2014 Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy