Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
10
questions
1
vote
1answer
52 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
26 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
31 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
152 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
112 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
62 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
293 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
98 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
52 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
198 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 ...
