Extension and its price for the connected vertex cover problem
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019), Extension and its price for the connected vertex cover problem, in Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia, Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings, Springer : Berlin Heidelberg, p. 315-326. 10.1007/978-3-030-25005-8_26
Type
Communication / ConférenceExternal document link
https://hal.archives-ouvertes.fr/hal-02344051Date
2019Conference title
Combinatorial Algorithms 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, ProceedingsConference date
2019Conference city
Berlin HeidelbergConference country
ITALYBook title
Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, ProceedingsBook author
Colbourn, Charles J.; Grossi, Roberto; Pisanti, NadiaPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-030-25004-1
Pages
315-326
Publication identifier
Metadata
Show full item recordAbstract (EN)
We consider extension variants of Vertex Cover and Independent Set, following a line of research initiated in [9]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G=(V,E) and a vertex set U⊆V , does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S, such that U⊆S (respectively, U⊇S ). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC, that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE), a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs.Subjects / Keywords
extension problems; connected vertex cover; upper con- nected vertex cover; price of extension; special graph classes; approxima- tion algorithms; NP-completenessRelated items
Showing items related by title and author.
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2022) Article accepté pour publication ou publié
-
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
-
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é