Questions tagged [vertex-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 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}...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-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?
user avatar
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?
user avatar
-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),...
user avatar
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 ...
user avatar
  • 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(...
user avatar
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$ ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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). ...
user avatar
  • 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 ...
user avatar
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? ...
user avatar
  • 17