Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
72
questions
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
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
25
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
30
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 ...
- 1
0
votes
0
answers
28
views
Given a graph and specific VC instance, find number of variables when reducing from VC to SAT
I have question already answered from past exam, and I'm trying to figure where my logic fails.
Given a graph find vertex cover of size 2.
The question is how many variables are there going to be for ...
- 219
1
vote
1
answer
124
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 ...
0
votes
0
answers
55
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 ...
- 503
0
votes
0
answers
92
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$ ...
- 103
0
votes
1
answer
216
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}...
- 282
1
vote
0
answers
163
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
55
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 ...
- 810
3
votes
0
answers
64
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
184
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
34
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 ...
- 31
0
votes
1
answer
132
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 ...
- 73
1
vote
1
answer
25
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 ...
- 649
2
votes
1
answer
134
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 ...
- 649
4
votes
1
answer
269
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
59
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
106
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
44
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
2
votes
0
answers
61
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 ...
- 21
0
votes
1
answer
32
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(...
- 157
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$ ...
- 373
-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
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
163
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
199
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 ...
- 577
1
vote
1
answer
73
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 ...
- 163
2
votes
1
answer
125
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
390
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,851
1
vote
1
answer
136
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
3k
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
227
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
309
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
3
votes
0
answers
447
views
Facility location on a tree
Question:
Given a tree representing a neighbourhood where each node is a house.
Assign an antenna to each node such that the whole tree is covered.
An antenna of strength 0 can only ...
- 31
1
vote
2
answers
168
views
Time complexity of Vertex Cover vs Clique for fixed k
I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm ...
- 169
0
votes
1
answer
55
views
Solving Independent Set through Vertex Cover
I have an Independent Set problem, in which I have to check if given graph has a IS of given size $k$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those ...
- 169
1
vote
1
answer
57
views
Variant of greedy algorithm for vertex cover
Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?
Input: $G = (V,E)$
Set $C \gets \emptyset$ and $E' \gets E$.
while $E' \neq \emptyset$...
- 11
0
votes
1
answer
51
views
Struggling with NP-Complete Problem
I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows:
The Set Cover problem is the following:
Instance: ...
2
votes
1
answer
210
views
A variant of hitting set problem? Is this also a NP-hard problem?
Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$, it is ...
- 21
0
votes
1
answer
347
views
Solving distance-d independent set in a simple way
I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). ...
- 169
3
votes
0
answers
52
views
Scheduling is NP-Hard via vertex cover
Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness?
Particularly looking for ...
0
votes
2
answers
668
views
Reducing Vertex Cover to Half Vertex Cover
I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:
Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?
...
- 17