14 votes
Accepted

A problem with the greedy approach to finding a maximal matching

You're correct, you're not missing anything -- except that the algorithm is not wrong. The task is to choose a maximal matching, not a maximum matching. There may be many possible maximal matchings, ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

Greedy algorithm for vertex cover

Start with a clique on the vertices $A,B,C,D$. Connect $A,B$ to a new vertex $a$. Connect $B,C$ to a new vertex $c$. Connect $a,c$ to a new vertex $b$. The vertex $b$ is the only one of degree 2, so ...
Yuval Filmus's user avatar
5 votes
Accepted

Vertex Cover of size at most $\log n$

If you solve Vertex Cover with the simple branching algorithm, you achieve an FPT running time of $2^k \text{poly}(n)$, where $k$ is an upper bound for the solution you are looking for. Substituting $...
Pål GD's user avatar
  • 16.1k
5 votes
Accepted

Vertex cover with covering radius 2

It is still NP-complete. It is easy to see it is in NP. To prove its NP-completeness, we reduce the standard vertex cover problem to this problem. Given an instance $G=(V,E)$ of vertex cover problem, ...
xskxzr's user avatar
  • 7,455
4 votes
Accepted

min vertex cover to access k edges in a tree

There is a $\mathcal{O}(nk)$ DP approach. Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the ...
Antti Röyskö's user avatar
4 votes

Greedy algorithm for vertex cover

Take $k$ copies of $C_4$, and attach them all to a single vertex. For instance, if $k=2$, you get the graph $X_{27}$ shown below (courtesy of graphclasses.org): A vertex cover of size $k+1$ can be ...
Anthony Labarre's user avatar
4 votes
Accepted

Finding a kernel for d-Bounded degree deletion

Reduction Rule 1. Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back ...
advocateofnone's user avatar
4 votes
Accepted

FPT algorithm for 1-BDD

Let $v$ be an arbitrary vertex in your graph, of degree $d$. In any solution $D$, either $v \in D$, or at least $d-1$ of its neighbors are in $D$. In this case, we have one branch with parameter $k-1$,...
Yuval Filmus's user avatar
4 votes
Accepted

Where does 1.3606 approximation ratio come from for vertex cover approximation?

The fact that nobody found a $1.99$ approximation doesn't necessarily mean that the problem of finding one is $\mathsf{NP}$-hard (e.g., it might be the case that that $\mathsf{P} \neq \mathsf{NP}$ and ...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Why is Independent Set "at least" and Vertex Cover "at most" k

Theory Note that the set of all vertices is trivially a vertex cover, and any set containing only one vertex is trivially an independent set. What is hard with an independent set is to make it larger. ...
Stef's user avatar
  • 530
4 votes

How to prove that this problem is NP Complete

Same class last semester: an edge between two vertices. Students in a circle: an hamiltonian cycle. I think you should be able to do the rest.
Nathaniel's user avatar
  • 15.5k
3 votes

Reducing Vertex Cover to Half Vertex Cover

Let special vertex cover be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover. Now suppose we're given an instance $G = (V,E),k$ of special ...
Yuval Filmus's user avatar
3 votes
Accepted

How to cover given entries in a matrix with minimum number of rows and columns?

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ ...
John L.'s user avatar
  • 39k
3 votes

Does the intersection of VC and CLIQUE belong to NPC?

The graphs with clique size at least $k$ and VC at most $k$ have a particular structure: They can be partitioned into three sets, $C$, $I$ and a singleton $\{s\}$; $G[C]$ is a clique, $G[I]$ is an ...
Pål GD's user avatar
  • 16.1k
3 votes
Accepted

Vertex cover of bipartite graph

As that link explains, you have one variable per edge in the maximum matching, call it $x_i$ for the $i$th edge. If $x_i=0$, we'll choose the left endpoint of that edge to be in the vertex cover; if $...
D.W.'s user avatar
  • 159k
3 votes

Vertex cover of bipartite graph

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this. In bipartite graphs, ...
Yuval Filmus's user avatar
3 votes

Greedy algorithm for vertex cover

Using the notation $[v](n_1,\ldots,n_k)$ to mean that because of vertex $v$ we remove its neighbors $n_1$ through $n_k$, your algorithm might remove vertices in the following way: $[2](1,5,7), [6](8), ...
Bernardo Subercaseaux's user avatar
3 votes

Approximation of Set Cover

Dinur and Steurer [1] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon > 0$. [1] ...
user3209423940248's user avatar
3 votes

Approximation of Set Cover

Clarification: When we say $\ln n$ is the best possible approximation for the set cover problem, we mean it for a general instance of the set cover. That is, there are set cover instances in which an ...
Inuyasha Yagami's user avatar
3 votes

How to determine the approximation factor for greedy vertex cover algorithm?

The approximation factor can be $\Omega(\log n)$. Consider a bipartite graph $G$ with a set $S_L$ with $n$ nodes on the left side. Also consider a collection of sets $S_{R,1},S_{R,2},\dots,S_{R,n}$ on ...
ErroR's user avatar
  • 1,910
3 votes
Accepted

Proving that the number of leaves in a tree >= number of unmatched vertices

Prove it by induction. It is true for trees with |V|<=3. Suppose that it is true for trees with |V|=n-1 and we want to prove it for a tree T with |V|=n. If there exist a leaf v which is unmatched ...
Majid Zohrehbandian's user avatar
3 votes
Accepted

Prove "Vertex Cover OR Clique" is NP complete

You can easily reduce from clique as follows. First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is ...
Tassle's user avatar
  • 2,522
2 votes

Partitioning vertices in a bipartite graph according to minimum vertex covers

The following idea comes from a Chinese blog. Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with ...
xskxzr's user avatar
  • 7,455
2 votes
Accepted

Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using ...
Yuval Filmus's user avatar
2 votes

Reduce Vertex Cover with size k to Vertex Cover with size n/2

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+...
xskxzr's user avatar
  • 7,455
2 votes

Minimum unweighted anticlique (independent set) cover / partition

This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. ...
taktoa's user avatar
  • 364
2 votes

Reducing Vertex Cover to Half Vertex Cover

In addition to the reduction given by Yuval Filmus, you can also use the following reduction, which avoids blowing up the size of $G$ to $\Theta(|V| \cdot |E|)$. Assume w.l.o.g. that $k<|V|$ (...
Steven's user avatar
  • 29.5k
2 votes

Connection between vertex cover and P=NP

I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time. We know that vertex cover is NP-hard to approximate within ...
STanja's user avatar
  • 438
2 votes
Accepted

Time complexity of Vertex Cover vs Clique for fixed k

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials. Plotting the curves is not so ...
Yuval Filmus's user avatar
2 votes

Why is the hitting set problem in NP

You cannot check, in general, whether $S'$ contains at least one element from each subset $C$ in polynomial time w.r.t. $n$. However, in order to show that the problem is NP it suffices to show that ...
Steven's user avatar
  • 29.5k

Only top scored, non community-wiki answers of a minimum length are eligible