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

### MAXIMUM TRIANGLE PACKING

- 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 Vi={ui,vi,wi}, , all three of the edges , , and belong to E.

- MEASURE: Cardinality of the triangle packing, i.e., the number of disjoint subsets Vi.

- Good News: Approximable within 3/2 for any [250].

- Bad News: APX-complete [265].

- Comment: Transformation from bounded MAXIMUM 3-DIMENSIONAL MATCHING. Admits a PTAS for planar graphs [50] and for -precision unit disk graphs [249]. Still APX-complete when the degree of G is bounded by 4 [265].

- Garey and Johnson: GT11