Efficient algorithms for the MAX k-VERTEX COVER problem

Given a graph G(V, E) of order n and a constant k <= n, the maxk- vertex cover problem consists of determining k vertices that cover the maximum number of edges in G. In its (standard) parameterized version, maxk- vertex cover can be stated as follows: “given G, k and parameter l, does G contain k vertices that cover at least l edges?”. We first devise moderately exponential exact algorithms for maxk- 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 maxk- vertex cover with complexity bounded above by the maximum among c^k and γ^τ , for some γ < 2, where τ is the cardinality of a minimum vertex cover of G (note that max k- vertex cover /∈ FPT with respect to parameter k unless FPT = W[1]), using polynomial space. We finally study approximation of maxk- vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.