# Questions tagged [vertex-cover]

The tag has no usage guidance.

82 questions
Filter by
Sorted by
Tagged with
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
43 views

1 vote
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
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 ...
1 vote
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
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 ...
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 ...
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$ ...
674 views

1 vote
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 ...
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$...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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?
1 vote
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?
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),...
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 ...
39 views

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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...