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.

свернуть