Skip to main content

Questions tagged [vertex-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
111 views

Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

The paper [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Austrin, Khot, Safra] Shows that assuming the Unique Game Conjecture (UGC) the minimum vertex cover problem ...
John's user avatar
  • 412
2 votes
1 answer
122 views

Enumerating all Vertex Covers of Size at most $k$

I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most $k$? Is there any algorithm that can achieve ...
Sugyani's user avatar
  • 23
0 votes
0 answers
93 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 ...
Chaithanya's user avatar
5 votes
0 answers
63 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) ...
xtyner's user avatar
  • 81
4 votes
2 answers
262 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. ...
reservoir's user avatar
4 votes
0 answers
97 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 ...
AngryLion's user avatar
  • 173
1 vote
3 answers
591 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 ...
SagarM's user avatar
  • 716
-1 votes
1 answer
166 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 ...
markHall's user avatar
3 votes
2 answers
816 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 ...
Saeed's user avatar
  • 3,440
7 votes
0 answers
240 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 ...
Yixin Cao's user avatar
  • 2,559