# Tag Info

Accepted

### Is the maximum independent set in cubic planar graphs NP-complete?

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper. Bojan Mohar: "Face Covers and the Genus Problem for Apex Graphs" Journal of ...
• 5,772

### Maximum Vertex Cover

Thanks @Neal Young for a nice solution. I already accepted your answer. I just wanted to point out, for future readers, where exactly I ''failed''. So, what I had already shown (using @Neil's ...
Accepted

### Maximum Vertex Cover

Recall that $L=\max_{S\subseteq V : |S|=k} \sum_{v\in S} d(v) / 2$, where $d(v)$ is the degree of vertex $v$, and that, as observed in the post, any set of $k$ vertices covers at most $2L$ edges. ...
• 10.8k
1 vote
Accepted

### approximate maximum clique given vertex cover

Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good. Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find ...
1 vote

### Is the maximum independent set in cubic planar graphs NP-complete?

Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., the answer here. Note that this gadget keeps planarity.
• 2,559

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