# Questions tagged [vertex-cover]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
312 views

### Greedy algorithm for vertex cover

Given a graph $G(V, E)$, consider the following algorithm: Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$) Let $v$ be one of the vertices with ...
92 views

### Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
25 views

### Why is the hitting set problem in NP

I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979): INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$. QUESTION: Does $S$ contains a ...
387 views

### Facility location on a tree

Question: Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered. An antenna of strength 0 can only ...
29 views

### Time complexity of Vertex Cover vs Clique for fixed k

I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$: - Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm) - Clique algorithm ...
32 views

### Solving Independent Set through Vertex Cover

I have an Independent Set problem, in which I have to check if given graph has a IS of given size $k$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those ...
34 views

### Variant of greedy algorithm for vertex cover

Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not? Input: $G = (V,E)$ Set $C \gets \emptyset$ and $E' \gets E$. while $E' \neq \emptyset$...
22 views

### Struggling with NP-Complete Problem

I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows: The Set Cover problem is the following: Instance: ...
52 views

### A variant of hitting set problem? Is this also a NP-hard problem?

Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$, it is ...
86 views

### Solving distance-d independent set in a simple way

I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). ...
41 views

### Scheduling is NP-Hard via vertex cover

Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness? Particularly looking for ...
191 views

### Reducing Vertex Cover to Half Vertex Cover

I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction: Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges? ...
19 views

### algorithm that finds minimal vertex cover of a given vertex

i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to. not sure on how to do it correctly, ...
19 views

### Reducing vertex cover to minimal vertex cover

What is a quick and a elegant way to reduce vertex cover to minimal vertex cover? Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
140 views

### Connection between vertex cover and P=NP

I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it. In an undirected graph $G(V,E)$, ...
808 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 ...
119 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$. ...
572 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 ...
174 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 ...
507 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, ...
238 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: ...
90 views

### set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
260 views

### Partitioning vertices in a bipartite graph according to minimum vertex covers

How to solve this problem? A vertex cover of a graph 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 ...
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 ...
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 ...