# Questions tagged [vertex-cover]

The tag has no usage guidance.

72 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
66 views

### Proving that the number of leaves in a tree >= number of unmatched vertices

Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every ...
• 331
1 vote
1 answer
31 views

### How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges

EVG is defined as EVC = { <G,m,k>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes} If EVG was decidable in polynomial time how could we find the ...
• 135
2 votes
1 answer
41 views

### Reduction from vertex-cover to system of quadratic equations

Define $$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$ and $$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$ I am ...
• 236
1 vote
1 answer
27 views

### Trivial vertex cover in regular graph is 2-approximation Proof

I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover. My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
• 149
1 vote
0 answers
35 views

### Prove that a dominating set has minimum cardinality in a "unit interval graph"

I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
• 149
1 vote
0 answers
86 views

1 vote
0 answers
163 views

0 votes
1 answer
49 views

### Vertex cover of minimal graph

I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
-1 votes
1 answer
69 views

### Is this exponential-sized vertex cover problem in P?

Suppose P $\neq$ NP. Prove or disprove if language is in P using a reduction or an algorithm: $$\left\{ \left(G = (V,E), k, 0^{2^{|V|}} \right) \mid (G,k) \in VC \right\}$$ Suppose I have the this ...
• 219
1 vote
1 answer
75 views

### What is the complexity class of finding vertex cover number of a simple graph?

Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...
• 3,497
1 vote
1 answer
21 views

### Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?

If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$‌ in quasi-polynomial time? As I found, we cannot find any ...
• 3,497
3 votes
1 answer
62 views

• 17