MAXIMUM TRIANGLE PACKING (original) (raw)

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

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.
_Good News:_Approximable within 3/2![$+\varepsilon ](http://www.csc.kth.se/ viggo/wwwcompendium/img132.gif)forany!for any ![](http://www.csc.kth.se/ viggo/wwwcompendium/img132.gif)forany!\varepsilon >0$[265].
_Bad News:_APX-complete [280].
_Comment:_Transformation from bounded MAXIMUM 3-DIMENSIONALMATCHING. 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

Viggo Kann
2000-03-20