# Questions tagged [vertex-cover]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
88 views

### Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
2k views

### Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...
736 views

### min vertex cover to access k edges in a tree

I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices. For example, if $N=9$ and $K=6$ and we have ...
536 views

### Derandomization of vertex cover algorithm

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$. Add to ...
90 views

### Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
163 views

66 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 ...