Journal
ALGORITHMICA
Volume 57, Issue 4, Pages 747-768Publisher
SPRINGER
DOI: 10.1007/s00453-008-9233-8
Keywords
Chordal graphs; Fixed-parameter tractability; Chordal deletion
Funding
- Magyary Zoltan Felsooktatasi Kozalapitvany
- Hungarian National Research Fund [67651]
Ask authors/readers for more resources
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)a <...n (alpha) for some constant alpha 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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available