Chordal editing is fixed-parameter tractable

chordal completion chordal deletion chordal graph clique tree decomposition graph modification problems holes parameterized computation simplicial vertex sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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

k_{1}

,

k_{2}

, and

k_{3}

, the extsc{chordal editing} problem asks whether

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 extsc{chordal vertex/edge deletion} and extsc{chordal completion} (also known as extsc{minimum fill-in}). Our main result is an algorithm for extsc{chordal editing} in time

2^{O (k l o g k)} c d o t n^{O (1)}

, where

k := k_{1} + k_{2} + k_{3}

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 extsc{chordal deletion}.

Recommendations

Cites work

Cited in

(46)

This page was built for publication: Chordal editing is fixed-parameter tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300460)