10 votes
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 ...
Gamow's user avatar
  • 5,772
5 votes

Minimum number of triangles required to cover a complete graph?

If $n$ is congruent to $1$ or $3$ modulo $6$, there is a covering of the complete graph $K_n$ with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly $\frac{1}{3}...
Peter Shor 's user avatar
4 votes
Accepted

Minimum number of triangles required to cover a complete graph?

Let $N(n)$ be the number of triangles needed to cover $K_n$. Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound. Note that ...
Tim's user avatar
  • 627
4 votes

Minimum number of triangles required to cover a complete graph?

This problem is the subject of (and was completely solved in) the paper "M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, ...
Nathaniel Johnston's user avatar
2 votes
Accepted

Enumerating all Vertex Covers of Size at most $k$

The algorithm fails in the case, when there are no edges left to cover, because then it does not have a structure to branch on. Consider for example the case where the graph is edgeless, then we have $...
Christian Komusiewicz's user avatar
2 votes

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 ...
reservoir's user avatar
2 votes
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. ...
Neal Young's user avatar
  • 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 ...
Nicolas GZ's user avatar
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.
Yixin Cao's user avatar
  • 2,559

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