The vertex-disjoint triangles problem

Abstract

The vertex-disjoint triangles (VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G. The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. It is known that the triangle cover problem is NP-complete on general graphs with clique number 3 [6]. The VDT problem is MAX SNP-hard on graphs with maximum degree four, while it can be approximated within 3/2 + epsilon, for any epsilon > 0, in polynomial time [11]. We prove that the VDT problem is NP-complete even when the input graphs are chordal, planar, line or total graphs. We present an O(m root n) algorithm for the VDT problem on split graphs and an O(n(3)) algorithm for the VDT problem on cographs. A linear algorithm for the triangle cover problem on strongly chordal graphs is also presented. Finally, the notion of packing-hardness, which may be crucial to the understanding of the difficulty of generalized matching problems, is defined.