Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019
DOI: 10.7155/jgaa.00519
Weighted Upper Edge Cover: Complexity and Approximability
Vol. 24, no. 2, pp. 6588, 2020. Regular paper.
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 wellknown that ${\rm M{\small INIMUM}}$ ${\rm E{\small DGE}}$ ${\rm C{\small OVER}}$ is polynomialtime solvable and the "flipped" version is NPhard, 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 edgeweighted 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 counterbalance these negative results by giving some positive approximation results in specific graph classes.

Submitted: April 2019.
Reviewed: June 2019.
Revised: July 2019.
Accepted: August 2019.
Final: January 2020.
Published: February 2020.

Journal Supporters
