GT11 M AXIMUM H-M ATCHING

     
• I NSTANCE : Graph and a fixed graph with at least three vertices in some connected component.
• S OLUTION : A H -matching for G , i.e., a collection of disjoint subgraphs of G , each isomorphic to H .
• M EASURE : Cardinality of the H -matching, i.e., the number of disjoint subgraphs .

• Good News: Approximable within for any [ 182 ].
• Bad News: A PX -hard [ 201 ].
• Comment: Transformation from bounded M AXIMUM 3-S ATISFIABILITY . Variation in which the degree of G is bounded by a constant B is A PX -complete [ 201 ]. Admits a PTAS for planar graphs [ 33 ], but does not admit an FPTAS [ 45 ].     Admits a PTAS for -precision unit disk graphs [ 181 ].     Induced M AXIMUM H-M ATCHING , i.e., where the subgraphs are induced subgraphs of G , has the same good and bad news as the ordinary problem, even when the degree of G is bounded.

  M AXIMUM M ATCHING OF C ONSISTENT K -C LIQUES is the variation in which H is a k -clique   and the vertices of G are partitioned into k independent sets , each is partitioned into some sets , and at most one vertex in each may be included in the matching. This problem is not in A PX for and is not approximable within 4/3 for . It is not in A PX for any unless NP QP [ 337 ].

• Garey and Johnson: GT12