The Price of Connectivity for Vertex Cover

Abstract : The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is always greater or equal to the vertex cover number. Connected vertex covers are found in many applications, and the relationship between those two graph invariants is therefore a natural question to investigate. For that purpose, we introduce the \em Price of Connectivity, defined as the ratio between the two vertex cover numbers. We prove that the price of connectivity is at most 2 for arbitrary graphs. We further consider graph classes in which the price of connectivity of every induced subgraph is bounded by some real number t. We obtain forbidden induced subgraph characterizations for every real value t ≤q 3/2. We also investigate critical graphs for this property, namely, graphs whose price of connectivity is strictly greater than that of any proper induced subgraph. Those are the only graphs that can appear in a forbidden subgraph characterization for the hereditary property of having a price of connectivity at most t. In particular, we completely characterize the critical graphs that are also chordal. Finally, we also consider the question of computing the price of connectivity of a given graph. Unsurprisingly, the decision version of this question is NP-hard. In fact, we show that it is even complete for the class Θ₂^P = P^NP[\log], the class of decision problems that can be solved in polynomial time, provided we can make O(\log n) queries to an NP-oracle. This paves the way for a thorough investigation of the complexity of problems involving ratios of graph invariants.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.207--223
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179215
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:15:06
Dernière modification le : mercredi 21 mars 2018 - 18:57:28
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:24:26

Fichier

dmtcs-16-1-13.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01179215, version 1

Collections

Citation

Eglantine Camby, Jean Cardinal, Samuel Fiorini, Oliver Schaudt. The Price of Connectivity for Vertex Cover. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.207--223. 〈hal-01179215〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

306