View source for Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem)

== Time Complexity == 

$O(kn + {1.2852}^k)$

== Space Complexity == 

$O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words

(First auxiliary graph contains O(k^2) edges; algorithm subsequently branches to a depth of O(k) (each fork being degree O(1)), with a new O(k^2)-sized graph at each depth. Interleaving shouldn't increase space usage asymptotically. (Could possibly be reduced to O(k) by just keeping track of graph deltas?) (but also a different source claims exponential?))

== Description == 



== Approximate? == 

Exact

== Randomized? == 

No, deterministic

== Model of Computation == 

Word RAM

== Year == 

2001

== Reference == 

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.4800&rep=rep1&type=pdf