Weighted Upper Edge Cover: Complexity and Approximability

Abstract

Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such "flipping" of the objective function was done for many classical optimization problems. For example, ${\rm M{\small INIMUM}}$ ${\rm V{\small ERTEX}}$ ${\rm C{\small OVER}}$ becomes ${\rm M{\small AXIMUM}}$ ${\rm M{\small INIMAL}}$ ${\rm V{\small ERTEX}}$ ${\rm C{\small OVER}}$, ${\rm M{\small AXIMUM}}$ ${\rm I{\small NDEPENDENT}}$ ${\rm S{\small ET}}$ becomes ${\rm M{\small INIMUM}}$ ${\rm M{\small AXIMAL}}$ ${\rm I{\small NDEPENDENT}}$ ${\rm S{\small ET}}$ and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called ${\rm U{\small PPER}}$ ${\rm E{\small DGE}}$ ${\rm C{\small OVER}}$, a problem having application in genomic sequence alignment. It is well-known that ${\rm M{\small INIMUM}}$ ${\rm E{\small DGE}}$ ${\rm C{\small OVER}}$ is polynomial-time solvable and the "flipped" version is NP-hard, but constant approximable. We show that the weighted ${\rm U{\small PPER}}$ ${\rm E{\small DGE}}$ ${\rm C{\small OVER}}$ is much more difficult than ${\rm U{\small PPER}}$ ${\rm E{\small DGE}}$ ${\rm C{\small OVER}}$ because it is not $O(\frac{1}{n^{1/2-\varepsilon}})$ approximable, nor $O(\frac{1}{\Delta^{1-\varepsilon}})$ in edge-weighted graphs of size $n$ and maximum degree $\Delta$ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and $k$-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.