Weighted Upper Edge Cover: Complexity and Approximability
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, MINIMUM VERTEX COVER becomes MAXIMUM MINIMAL VERTEX COVER , MAXIMUM INDEPENDENT SET becomes MINIMUM MAXIMAL INDEPENDENT SET and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called UPPER EDGE COVER , a problem having application in genomic sequence alignment. It is well-known that MINIMUM EDGE COVER is polynomial-time solvable and the "flipped" version is NP-hard, but constant approximable. We show that the weighted UPPER EDGE COVER is much more difficult than UPPER EDGE COVER because it is not O(1n^1/2-ε ) approximable, nor O(1Δ^1-ε ) in edge-weighted graphs of size n and maximum degree Δ 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., number=2, journal=Journal of Graph Algorithms and Applications, author=Khoshkhah, Kaveh and Khosravian Ghadikolaei, Mehdi and Monnot, Jérôme and Sikora, Florian, year=2020, month=Feb., pages=65–88