9

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 Combinatorial Theory, Series B 82, 102-117 (2001)


3

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 the case $n=2$ is degenerate, as $K_2$ has only one edge and no triangles. In the following analysis, I will allow myself to use triangles that cover only one ...


1

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}\binom{n}{2}$ triangles. This is called a Steiner triple system and the answers to this Math Overflow question give some ways to construct Steiner triple ...


1

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 it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.


1

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.


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