Discrete Mathematics & Theoretical Computer Science 
We consider the problems of finding the maximum number of vertexdisjoint triangles (VTP) and edgedisjoint triangles (ETP) in a simple graph. Both problems are NPhard. The algorithm with the best approximation guarantee known so far for these problems has ratio $3/2 + ɛ$, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APXhard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact lineartime algorithm for VTP on the class of indifference graphs.
Source : ScholeXplorer
IsRelatedTo DOI 10.1016/j.endm.2009.11.032 Source : ScholeXplorer IsRelatedTo DOI 10.46298/dmtcs.533 Source : ScholeXplorer IsRelatedTo HANDLE 11336/68193
