MAXIMUM TRIANGLE PACKING

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A triangle packing for G, i.e., a collection $V_1,V_2,\ldots,V_k$ of disjoint subsets of V, each containing exactly 3 vertices, such that for each $V_i=\{u_i,v_i,w_i\}$, $1\le i\le k$, all three of the edges $\left<u_i,v_i\right>$, $\left<u_i,w_i\right>$, and $\left<v_i,w_i\right>$ belong to E.
• MEASURE: Cardinality of the triangle packing, i.e., the number of disjoint subsets $V_i$.

  
  

• Good News: Approximable within 3/2$+\varepsilon$ for any $\varepsilon >0$ [265].
• Bad News: APX-complete [280].
• Comment: Transformation from bounded MAXIMUM 3-DIMENSIONAL MATCHING. Admits a PTAS for planar graphs [53] and for $\lambda$-precision unit disk graphs [264]. Still APX-complete when the degree of G is bounded by 4 [280].
• Garey and Johnson: GT11