Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
82
questions
-2
votes
1
answer
24
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.
- 315
-1
votes
1
answer
35
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
48
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
0
votes
0
answers
15
views
least collection of node disjoint paths that cover a given set of vertices
Given a directed graph G (with cycles) with source and target, and a set of interested vertices S.
we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
-1
votes
1
answer
253
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
58
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
81
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
43
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) \...
0
votes
1
answer
161
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
103
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 ...
- 413
1
vote
1
answer
52
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
119
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 ...
- 258
1
vote
1
answer
116
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
49
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
928
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
77
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
42
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
347
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 ...
1
vote
1
answer
257
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 ...
- 113
0
votes
0
answers
98
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 ...
- 594
0
votes
0
answers
135
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
0
votes
1
answer
674
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}...
- 294
1
vote
0
answers
195
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
205
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 ...
- 838
3
votes
0
answers
76
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
422
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
179
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
38
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
157
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
311
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
70
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
253
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
49
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
138
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
39
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(...
- 267
0
votes
1
answer
53
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
87
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
144
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,562
1
vote
1
answer
37
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,562
3
votes
1
answer
80
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
285
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
348
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 ...
- 613
1
vote
1
answer
101
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
643
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 ...
- 131
4
votes
1
answer
598
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,933
1
vote
1
answer
275
views
Bipartite maximum matching with added constraints
Suppose you have two lists as follows
List $A$ = $(a_1, a_2, ..., a_m)$
List $B$ = $(b_1, b_2, ..., b_n)$
Each element in list $A$ can be paired with many or no elements in list $B$. I have a function ...
- 111
1
vote
3
answers
4k
views
Greedy algorithm for vertex cover
Given a graph $G(V, E)$, consider the following algorithm:
Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
Let $v$ be one of the vertices with ...
3
votes
1
answer
356
views
Minimum vertex cover algorithm with linear programming
Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
0
votes
1
answer
527
views
Why is the hitting set problem in NP
I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):
INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.
QUESTION: Does $S$ contains a ...
- 143