Finding k Disjoint Triangles in an Arbitrary Graph
Journal article, Peer reviewed
Accepted version
View/ Open
Date
2004Metadata
Show full item recordCollections
Original version
Lecture Notes in Computer Science vol 3353, 235-244. https://doi.org/10.1007/978-3-540-30559-0_20Abstract
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.