We provide a fixed-parameter certifying algorithm for the Vertex-deletion problem. An upper bound for the size of the forbidden set for C+kv is shown demonstrating that, for all hereditary classes C characterised by a finite forbidden set, the class C+kv is characterised by a finite forbidden set. The certifying algorithm runs in time O(f(k) · n~c) and can be verified in O(n~c) in the affirmative case and O(f(k)) in the negative case. This is the first known fixed-parameter certifying algorithm, as far as the authors are aware.
展开▼
