Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [vertex-cover]

The tag has no usage guidance.

0
votes
0answers
18 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
124 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
101 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
55 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
192 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
84 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
44 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
165 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 ...