We meet Vertex Cover but this time with a new, "above guarantee" parameter. The algorithm uses ideas from things we have seen before - the LP-based kernel and the second branching algorithm for vertex cover, but the analysis depends on how the LPOPT evolves as the graph changes due to our branching and reduction actions.
![](https://s2.save4k.ru/pic/OgRMP2XpOyI/maxresdefault.jpg)