The Price of Connectivity for Vertex Cover
Eglantine Camby, Jean Cardinal, Samuel Fiorini, Oliver Schaudt
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 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 ≤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
Θ2P = PNP[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.
Full Text: PDF PostScript