Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
8
questions
0
votes
0
answers
58
views
Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover
This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
- 11
5
votes
0
answers
59
views
W[t]-containment of partial covering problems
I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
- 81
4
votes
2
answers
243
views
Maximum Vertex Cover
I recently encountered the following exam problem: Given an undirected graph $G := (V,E)$ and a natural number $k \geq 1$, we want to cover as many edges as possible using exactly $k$ vertices. ...
- 89
4
votes
0
answers
91
views
Reducing counting minimal vertex covers to counting minimum cardinality vertex covers
Consider two problems.
Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$.
Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
- 173
0
votes
2
answers
437
views
Minimum number of triangles required to cover a complete graph?
Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would ...
- 706
-1
votes
1
answer
147
views
approximate maximum clique given vertex cover
I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G ...
- 1
3
votes
2
answers
723
views
Is the maximum independent set in cubic planar graphs NP-complete?
In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
- 3,440
7
votes
0
answers
239
views
Can we achieve a better kernel for the Vertex Cover problem on planar graphs?
We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.
My question is, can we do better for planar graphs? It is easy ...
- 2,560