Efficient algorithms for the max $$k$$ -vertex cover problem

Given a graph $$G(V,E)$$ of order $$n$$ and a constant $$k \leqslant 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 $$\ell ,$$ does $$G$$ contain $$k$$ vertices that cover at least $$\ell $$ 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 $$c^k$$ and $$\gamma ^{\tau },$$ for some $$\gamma