Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
6
questions
4
votes
2
answers
231
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
83
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 ...
- 163
0
votes
2
answers
335
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
133
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
596
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,430
7
votes
0
answers
237
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