Finding k Disjoint Triangles in an Arbitrary Graph

Abstract

We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K 3 (the triangle) we give an O(22klog k + 1.869k n 2) algorithm, and for general H an O(2k|H|logk + 2k|H|log |H| n |H|) algorithm. We introduce a preprocessing (kernelization) technique based on crown decompositions of an auxiliary graph. For H=K 3 this leads to a preprocessing algorithm that reduces an arbitrary input graph of the problem to a graph on O(k 3) vertices in polynomial time.