<p>Node-weighted multiway-cut is a problem to which vertex-cover can be reduced to in an approximation preserving way. Thus, a better than $2$-approximation for node-weighted multiway cut is not possible assuming UGC. The reduction was shown by Garg-Vazirani-Yannakakis in their paper which also established a $2$-approximation for node-weighted multiway-cut.</p>

CC BY-SA 4.0
2024-08-22T13:28:36.230Z
Feedback Vertex Set is perhaps a more natural problem. Give a graph $G=(V,E)$ we wish to remove the fewest number of vertices so that the residual graph is a forest (no cycles). In other words FVS is a hitting set for all cycles in the graph. There is a 2-approximation for (weighted) FVS and VC reduces easily in an approximation preserving fashion.
Chandra Chekuri
CC BY-SA 3.0
2011-11-07T22:51:12.920Z
2011-11-07T22:51:12.920Z
Chandra Chekuri
<p>Are there any problems $P$ such that an $\alpha$-approximation for $P$ (for soem choice of $\alpha$) would imply a better than 2-approximation for VERTEX COVER, which would be hard via the UGC ?  </p>

<cc.complexity-theory><unique-games-conjecture>
Problems that are hard w.r.t UGC-hardness of VERTEX COVER
Suresh Venkat
# Problems that are hard w.r.t UGC-hardness of VERTEX COVER

(Asked by: username_0 on 2011-11-07)

Are there any problems $P$ such that an $\alpha$-approximation for $P$ (for soem choice of $\alpha$) would imply a better than 2-approximation for VERTEX COVER, which would be hard via the UGC ?

**Tags:** cc.complexity-theory, unique-games-conjecture


---

## 1 answers

### Answer by username_1 on 2011-11-07. Score: 12 | Accepted answer

Node-weighted multiway-cut is a problem to which vertex-cover can be reduced to in an approximation preserving way. Thus, a better than $2$-approximation for node-weighted multiway cut is not possible assuming UGC. The reduction was shown by Garg-Vazirani-Yannakakis in their paper which also established a $2$-approximation for node-weighted multiway-cut.

> **Comments:**
> **username_1**: Feedback Vertex Set is perhaps a more natural problem. Give a graph $G=(V,E)$ we wish to remove the fewest number of vertices so that the residual graph is a forest (no cycles). In other words FVS is a hitting set for all cycles in the graph. There is a 2-approximation for (weighted) FVS and VC reduces easily in an approximation preserving fashion.  

---

