Questions tagged [vertex-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
47 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 \...
csTheoryBeginner's user avatar
2 votes
1 answer
21 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 ...
Dar954826's user avatar
-2 votes
1 answer
32 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.
Aishgadol's user avatar
  • 345
-1 votes
1 answer
48 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 ...
PatrickBateman's user avatar
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 ...
Henning Koehler's user avatar
-1 votes
1 answer
611 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 ...
ConScience's user avatar
0 votes
0 answers
72 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 ...
alwayscurious's user avatar
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 ...
Anonymous Molecule's user avatar
0 votes
1 answer
75 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) \...
codeing_monkey's user avatar
0 votes
1 answer
237 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 ...
Akiles's user avatar
  • 3
2 votes
1 answer
116 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 ...
SVMteamsTool's user avatar
1 vote
1 answer
63 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 ...
Niv's user avatar
  • 165
2 votes
1 answer
189 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 ...
Tom Finet's user avatar
  • 258
1 vote
1 answer
167 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 ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
59 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 ...
NiRvanA's user avatar
  • 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 \...
kd8's user avatar
  • 11
1 vote
0 answers
89 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, ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
54 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 ...
bbb3321's user avatar
  • 87
1 vote
1 answer
489 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 ...
Archaeopteryx's user avatar
2 votes
1 answer
405 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 ...
nicetyartwork's user avatar
0 votes
0 answers
107 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 ...
AspiringMat's user avatar
0 votes
0 answers
152 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$ ...
JoshHalas's user avatar
  • 203
0 votes
1 answer
934 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}...
curiouscupcake's user avatar
1 vote
0 answers
202 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 $...
giorgioh's user avatar
  • 317
1 vote
1 answer
285 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 ...
xdavidliu's user avatar
  • 858
3 votes
0 answers
77 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$...
Dabbler's user avatar
  • 31
1 vote
1 answer
617 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 ...
micmic's user avatar
  • 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 ...
pensee's user avatar
  • 131
0 votes
1 answer
194 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 ...
John19's user avatar
  • 63
1 vote
1 answer
47 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 ...
heretoinfinity's user avatar
2 votes
1 answer
169 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 ...
heretoinfinity's user avatar
4 votes
1 answer
321 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 ...
Jumanji Halastra's user avatar
-2 votes
1 answer
82 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?
thatUser's user avatar
1 vote
1 answer
304 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?
thatUser's user avatar
-1 votes
1 answer
51 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),...
hash man's user avatar
3 votes
0 answers
158 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 ...
Eugenio's user avatar
  • 31
0 votes
1 answer
47 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(...
Michal Dvořák's user avatar
0 votes
1 answer
54 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$ ...
ChaosPredictor's user avatar
-1 votes
1 answer
89 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 ...
user6394019's user avatar
1 vote
1 answer
166 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 ...
OmG's user avatar
  • 3,572
1 vote
1 answer
49 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 ...
OmG's user avatar
  • 3,572
3 votes
1 answer
83 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 $...
temp3318's user avatar
2 votes
2 answers
398 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 ...
Mark97's user avatar
  • 41
3 votes
0 answers
554 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 ...
Blanco's user avatar
  • 623
1 vote
1 answer
105 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 ...
Sepehr Omidvar's user avatar
2 votes
1 answer
980 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 ...
calveeen's user avatar
  • 141
4 votes
1 answer
678 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 ...
advocateofnone's user avatar
2 votes
1 answer
341 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 ...
fardeem's user avatar
  • 121
1 vote
3 answers
5k 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 ...
Mario Giambarioli's user avatar
3 votes
1 answer
401 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 ...
Mario Giambarioli's user avatar