Efficient algorithms for the Max k-Vertex Cover problem

International audienceGiven a graph G(V,E) of order n and a constant k⩽n , the max k -vertex cover problem consists of determining k vertices that cover the maximum number of edges in G . In its (standard) parameterized version, max k -vertex cover can be stated as follows: “given G, k and parameter ℓ, does G contain k vertices that cover at least ℓ edges?”. We first devise moderately exponential exact algorithms for max k -vertex cover, with time-complexity exponential in n but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max k -vertex cover with complexity bounded above by the maximum among ck and γτ, for some γ