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
.
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].
.
of
disjoint subsets of V, each containing exactly 3 vertices, such that
for each
,
,
all three of the edges
,
,
and
belong to E.
.
for any
[265].
-precision unit disk graphs [264].
Still APX-complete when the degree of G is bounded by 4 [280].