The Price of Connectivity for Vertex Cover
The Price of Connectivity for Vertex Cover
复制标题
Vertex Cover 连接的价格
DOI：
--
复制
发表时间：
2013
影响因子：
0.7
通讯作者：
Oliver Schaudt
中科院分区：
文献类型：
--
作者：
Eglantine Camby;J. Cardinal;Samuel Fiorini;Oliver Schaudt
图形的顶点盖数是覆盖所有边缘所需的最小顶点数量。在许多应用中发现了连接的顶点覆盖物，因此这两个图形之间的关系是一个自然的问题。引入连接性的EM价格，定义为两个顶点封面数字之间的比率。通过一些实际数字，我们获得了每个实际值T≤Q3/2的禁止诱导子图。连通性严格大于任何适当的诱发子图的连接。同样，我们还考虑了计算给定图的连接价格的问题。我们表明，对于可以在多项式时间解决的决策问题类别的类别θ₂^p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = p = np-Oracle，我们甚至是完整的。这为彻底研究涉及图形不变的问题的复杂性的复杂性铺平了道路。
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.