# Tag Info

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, ...
• 159k
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 ...
• 277k
Accepted

• 159k

### 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, ...
• 277k

• 7,455

### 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. ...
• 364

### 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|$ (...
• 29.5k

### 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 ...
• 438
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 ...
• 277k
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 ...