Definition
Maximum Vertex Coverage Optimisation Problem
Instance: A finite simple undirected graph and a nonnegative integer .
Feasible solutions: Vertex sets with .
Objective: Maximise the number of covered edges:
\operatorname{cov}(X)=\{e\in E:e\cap X\neq\varnothing\}.$$ An edge is counted once if at least one endpoint is selected. This is the graph version of Maximum Coverage, also called Maximum $k$-Vertex Cover; edges, not vertices, are the objects being covered.