Next: MAXIMUM H-MATCHING
Up: Covering and Partitioning
Previous: MINIMUM MAXIMAL MATCHING
A triangle packing for G, i.e., a collection
disjoint subsets of V, each containing exactly 3 vertices, such that
all three of the edges
belong to E.
Cardinality of the triangle packing, i.e., the number of disjoint subsets
- Good News:
Approximable within 3/2
- Bad News:
Transformation from bounded MAXIMUM 3-DIMENSIONAL
Admits a PTAS for planar graphs 
and for -precision unit disk graphs .
Still APX-complete when the degree of G is bounded by 4 .
- Garey and Johnson: GT11