
Weighted Upper Edge Cover: Complexity and Approximability
Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2020), Weighted Upper Edge Cover: Complexity and Approximability, Journal of Graph Algorithms and Applications, 24, 2, p. 65-68. 10.7155/jgaa.00519
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
Journal of Graph Algorithms and ApplicationsVolume
24Number
2Publisher
Brown University
Pages
65-68
Publication identifier
Metadata
Show full item recordAbstract (EN)
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(1n1/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.Subjects / Keywords
Complexity; ApproximabilityRelated items
Showing items related by title and author.
-
Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
-
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
-
Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2020) Communication / Conférence
-
Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian (2019) Communication / Conférence
-
Sikora, Florian; Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme (2020) Article accepté pour publication ou publié