# Questions tagged [vertex-cover]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
687 views

### A problem with the greedy approach to finding a maximal matching

Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following ...
32 views

### Worst Case running time of the Minimum Vertex Cover Approximation algorithm

Considering this factor $2$ minimum vertex cover approximation algorithm : Repeat while there is an edge: Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. ...
45 views

### Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

Given a graph $G=(V,E)$ with $|V|=n,|E|=m$. I am reading a $\textit{brute force}$ solution to determining whether each candidate vertex cover of size $k \leq n$ is a vertex cover. The graph does not ...
52 views

### Bipartite graph minimal amount of vertices required

I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the ...
57 views

### Give an example of a connected graph where α(G) =100 and β(G) = 200

So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.
28 views

### Another vertex cover question?

I'm not sure this is equivalent to bipartite vertex cover question. The question is: Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex ...
37 views

### Dominating Set Gap Problem Reduction

In the reduction from Vertex Cover problem to Dominating Set a new vertex is added for each edge in the original graph. Specifically, Given graph $G=(V,E)$ where $|V|=n$ with $VC$ with size $k$ we ...
164 views

### Vertex Cover of size at most $\log n$

Consider the following language: $$L = \{ G | G \text{ has a VC of size at most } \log n \}$$ Does $L\in P$ or $L\in NPC$?
117 views

### Does the intersection of VC and CLIQUE belong to NPC?

Define: $$L=\{(G,k) : G\text{ has a vertex cover of size at most k, and a clique of size at least k}\}$$ I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that \$L\...
64 views

### 2-sat and vertex cover [duplicate]

I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of ...
358 views

### Vertex cover of bipartite graph

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality. From codeforces, ...
137 views

### Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC

Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover. Define ALG: ...