Chordal Deletion is Fixed-Parameter Tractable |
| |
Authors: | Dániel Marx |
| |
Affiliation: | 1. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, 1521, Hungary
|
| |
Abstract: | It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)⋅n
α
for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(n
k
) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math.
127:415–429, 2003). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|