** Next:** MAXIMUM H-MATCHING
** Up:** Covering and Partitioning
** Previous:** MINIMUM MAXIMAL MATCHING
** Index**

- INSTANCE:
Graph
.
- SOLUTION:
A triangle packing for
*G*, i.e., a collection
of
disjoint subsets of *V*, each containing exactly 3 vertices, such that
for each
,
,
all three of the edges
,
,
and
belong to *E*.
- MEASURE:
Cardinality of the triangle packing, i.e., the number of disjoint subsets
.

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

*Viggo Kann*

*2000-03-20*