Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
24
questions
0
votes
0answers
16 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
16 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
48 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
752 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
111 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
551 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
165 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
39 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
711 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
51 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
86 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
62 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
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.
2
votes
1answer
30 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 ...
0
votes
0answers
41 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 ...
2
votes
1answer
189 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
124 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
411 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
162 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
68 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
223 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 ...
4
votes
1answer
89 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
2answers
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 ...
