Geodesic
Weighted Upper Edge Cover: Complexity and Approximability
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019 , Tome 24 (2020) no. 2, pp. 65-88.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00519
Keywords: Maximum Minimal Edge Cover, Graph optimization problem, Computational Complexity, Approximability 
@article{JGAA_2020_24_2_a1,
     author = {Kaveh Khoshkhah and Mehdi Khosravian Ghadikolaei and J\'er\^ome Monnot and Florian Sikora},
     title = {Weighted {Upper} {Edge} {Cover:} {Complexity} and {Approximability}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {65--88},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2020},
     doi = {10.7155/jgaa.00519},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00519/}
}
TY  - JOUR
AU  - Kaveh Khoshkhah
AU  - Mehdi Khosravian Ghadikolaei
AU  - Jérôme Monnot
AU  - Florian Sikora
TI  - Weighted Upper Edge Cover: Complexity and Approximability
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 65
EP  - 88
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00519/
DO  - 10.7155/jgaa.00519
LA  - en
ID  - JGAA_2020_24_2_a1
ER  - 
%0 Journal Article
%A Kaveh Khoshkhah
%A Mehdi Khosravian Ghadikolaei
%A Jérôme Monnot
%A Florian Sikora
%T Weighted Upper Edge Cover: Complexity and Approximability
%J Journal of Graph Algorithms and Applications
%D 2020
%P 65-88
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00519/
%R 10.7155/jgaa.00519
%G en
%F JGAA_2020_24_2_a1
Kaveh Khoshkhah; Mehdi Khosravian Ghadikolaei; Jérôme Monnot; Florian Sikora. Weighted Upper Edge Cover: Complexity and Approximability. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 13th International Conference and  Workshops on Algorithms and Computation, WALCOM 2019
					, Tome 24 (2020) no. 2, pp. 65-88. doi : 10.7155/jgaa.00519. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00519/

Cité par Sources :