Questions tagged [vertex-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
28 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
146 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
106 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
59 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
238 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
90 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
49 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
184 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 ...