Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
35
questions
0
votes
3answers
368 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 ...
2
votes
1answer
98 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 ...
0
votes
1answer
26 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 ...
2
votes
0answers
392 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 ...
1
vote
2answers
32 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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$...
0
votes
1answer
23 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: ...
2
votes
1answer
58 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 ...
0
votes
1answer
91 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). ...
3
votes
0answers
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 ...
0
votes
2answers
196 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?
...
0
votes
0answers
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, ...
0
votes
1answer
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? ...
1
vote
1answer
143 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)$, ...
1
vote
2answers
817 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 ...
8
votes
0answers
122 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$.
...
1
vote
1answer
573 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 ...
1
vote
1answer
174 views
Error lower-bound for an algorithm for vertex cover
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 = \...
2
votes
1answer
56 views
Minimum unweighted anticlique (independent set) cover / partition
Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
4
votes
1answer
812 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 ...
1
vote
1answer
153 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. ...
2
votes
1answer
153 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 ...
2
votes
2answers
76 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 ...
1
vote
1answer
58 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.
2
votes
1answer
33 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 ...
2
votes
1answer
239 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$?
4
votes
1answer
128 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\...
0
votes
0answers
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 ...
-1
votes
2answers
511 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,
...
0
votes
0answers
239 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: ...
0
votes
1answer
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 ...
1
vote
1answer
264 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 ...
4
votes
1answer
95 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 ...
4
votes
3answers
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 ...
