Extension and its price for the connected vertex cover problem

Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris

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érence

External document link

https://hal.archives-ouvertes.fr/hal-02344051

Date

2019

Conference title

Combinatorial Algorithms 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, Proceedings

Conference date

2019

Conference city

Berlin Heidelberg

Conference country

ITALY

Book title

Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings

Book author

Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia

Publisher

Springer

Published in

Berlin Heidelberg

ISBN

978-3-030-25004-1

Pages

315-326

Abstract (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-completeness