Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
86
questions
4
votes
2
answers
62
views
Vertex cover approximation: what's wrong with max-degree heuristic?
For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
- 141
0
votes
0
answers
27
views
Adding edges to enlarge vertex cover
Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
- 555
1
vote
1
answer
150
views
Prove "Vertex Cover OR Clique" is NP complete
Instance: An undirected graph $G$ and a positive integer $k$
Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$?
Obviously, this problem is solved by polynomial ...
- 91
2
votes
1
answer
50
views
Min sum vertex cover complexity proof
One version of the minimum sum vertex cover [1] is the following problem:
We are given an undirected graph $G(V, E)$, and let $n = |V|$. The task is to find a bijective function $\psi: V \rightarrow \...
- 393
2
votes
1
answer
25
views
Parametrized threshold for LP Approximation in Vertex Cover Problem
I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.
The linear programming ...
- 21
-2
votes
1
answer
33
views
Is this considered a vertex cover?
I'm unsure if this satisfies the definition of vertex cover, the graph is unweighted and undirected:
if not, an explanation would be super enlighting.
- 365
-1
votes
1
answer
54
views
if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?
if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER?
the implication should be true because independent is ...
3
votes
1
answer
50
views
Vertex Cover on Comparability Graphs
Is there anything known about the hardness of Vertex Cover on the subclass of comparability graphs? In particular, is it known whether the problem is still NP-hard?
Related Results: In "Modular ...
- 151
-1
votes
1
answer
864
views
How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
- 25
0
votes
0
answers
74
views
Can I find the smallest vertex cover
so this is my question:-
If I manage to find a vertex cover which has ....let's say 100 more vertex than the minimum vertex cover. Can I find the minimum vertex cover in polynomial time from this ...
0
votes
1
answer
104
views
How to prove that this problem is NP Complete
I have a problem set about NP Completeness proofs and I'm struggling to approach this problem:
An organizer would like to arrange all the participants in a
circle where neighboring two students must ...
0
votes
1
answer
85
views
LP Approximation for Vertex Cover Problem
In Cormen's Introduction to Algorithms, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align*}
&\sum\limits_{v \in V}w(v)x(v) \...
- 306
0
votes
1
answer
317
views
Reducing Vertex Cover (or Independent Set) to Vertex Cover and Independent Set at the same time
In order to show that the next problem is NP-hard:
Problem: Vertex Cover and Independent Set
Input: Graph G and integer k
Output: Does G have a vertex cover of k and an independent set of k?
The sets ...
- 3
2
votes
1
answer
119
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 ...
- 443
1
vote
1
answer
64
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 ...
- 165
2
votes
1
answer
212
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 ...
- 268
1
vote
1
answer
217
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 ...
- 159
1
vote
0
answers
65
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 ...
- 159
1
vote
0
answers
2k
views
Hitting set problem and Vertex Cover
In Chapter 8 Question 5 of Kleinberg and Tardos, the problem is as follows:
Consider a set $A = \{a_1, \ldots , a_n\}$ and a collection $B_1, B_2, \ldots , B_m$ of subsets of $A$ (i.e., $B_i \...
- 11
1
vote
0
answers
97
views
Covering Salesman Problem (CSP) polynomial reduction to the TSP
I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP).
So, let me first define the CSP. The CSP, I am working on, ...
1
vote
1
answer
58
views
Vertex cover in a special graph
We say that an undirected graph $G=(V, E)$ is special if for every vertex $v\in V$ and edge $\{u, w\}\in E$, it holds that $\{v, u\}\in E$ or $\{v, w\}\in E$. In other words, a graph is special if for ...
- 87
1
vote
1
answer
548
views
Reduction of K-Vertex-Cover to SAT: How to define the constraint?
Overall, one would naturally think that with n different nodes, and for x(1) for example representing node 1, it would be like:
x(1)+x(2)+x(3)...+x(n) <= k
This would mean that for every possible ...
2
votes
1
answer
481
views
Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:
Given a graph G and a number k, does G contain an independent set of size at least k?
Given a graph G and a ...
- 123
0
votes
0
answers
112
views
Minimum weight $k-$path cover on a DAG proof verification
Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an
integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
- 613
0
votes
0
answers
163
views
Proving that a problem is not FPT using reduction
In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
- 203
2
votes
1
answer
1k
views
How to determine the approximation factor for greedy vertex cover algorithm?
The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left.
Formally:
$\text{GreedyVertexCover}...
- 314
1
vote
0
answers
209
views
Fixed Parameter Tractable for Special Vertex Cover using ILP
The problem I'm trying to solve reads as follows:
Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
- 317
1
vote
1
answer
341
views
why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?
I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in ...
- 858
3
votes
0
answers
78
views
Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them
Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$...
- 31
1
vote
1
answer
705
views
Is Vertex Cover of size $k >100$ polynomial time solvable?
I know that when we want to find out if Vertex Cover of size $k$ when $k
\leq C$, belongs to P or not (when $C$ is some constant), we actually
can find algorithm with polynomial time complexity (in ...
- 11
1
vote
0
answers
42
views
Show that if vertex cover is reducible to a mod-inverse than P=NP
Let MOD-INVERSE consist of all pairs $\langle N,c \rangle$ such that $c$ has an inverse modulo $N$.
Let VERTEX-COVER consist of all pairs $\langle G,k \rangle$ such that $G$ is an undirected graph ...
- 131
0
votes
1
answer
206
views
Kernelization algorithm for the following problem
We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
- 63
1
vote
1
answer
50
views
Are disjoint edges the same as matchings?
I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings.
To support this, I am also watching ...
- 659
2
votes
1
answer
190
views
Where does 1.3606 approximation ratio come from for vertex cover approximation?
I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.
Later, the professor asks if we can do any better. The lecturer went on to say that ...
- 659
4
votes
1
answer
322
views
FPT algorithm for 1-BDD
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at
most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is ...
-2
votes
1
answer
84
views
Dominating set with vertex cover
if we have a Graph (V, E) and for all nodes v_i, v_j exists a path from v_i to v_j can you give me an example of such graph with dominating set size 2 and doesn't have a vertex cover of size 3?
- 11
1
vote
1
answer
363
views
Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?
If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?
- 11
-1
votes
1
answer
52
views
Reduction from $VC$ to $CD$
We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor),...
- 13
3
votes
0
answers
171
views
3-cycle cover decision problem for directed graphs: best known algorithm and maximum size of tractable problems
I know that the 3-cycle cover decision problem for directed graphs (3-DCC), defined as finding whether a directed graph has a disjoint vertex cycle cover in which every cycle has at least 3 edges, is ...
- 31
0
votes
1
answer
49
views
Structural parametrization for weighted vertex cover
Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(...
- 575
0
votes
1
answer
55
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$ ...
- 373
-1
votes
1
answer
91
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 ...
- 217
1
vote
1
answer
183
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,582
1
vote
1
answer
51
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,582
3
votes
1
answer
86
views
A question about the work per recursive call in FPT vertex cover of size k algorithm
I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:
VertexCoverFPT$(G, k)$
if $G$ has no edges then return true
if $...
- 33
2
votes
2
answers
449
views
Approximation of Set Cover
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better ...
- 41
3
votes
0
answers
610
views
Is there any polytime reduction from feedback vertex set to vertex cover?
I know that feedback vertex set (FVS) problem is $\mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS.
Specifically, given a undirected ...
- 623
1
vote
1
answer
107
views
Number of vertices of a graph in vertex cover of size $m$
Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices.
Note: Remove all vertices of degree $0$.
Answer:
The idea is to ...
- 173
2
votes
1
answer
1k
views
Approximate LP for vertex cover problem
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
- 141
4
votes
1
answer
762
views
Finding a kernel for d-Bounded degree deletion
In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum ...
- 2,992