MAXIMUM H-MATCHING

• INSTANCE: Graph $G=\left(V_G,E_G\right)$ and a fixed graph $H=\left(V_H,E_H\right)$ with at least three vertices in some connected component.
• SOLUTION: A H-matching for G, i.e., a collection $G_1,G_2,\ldots,G_k$ of disjoint subgraphs of G, each isomorphic to H.
• MEASURE: Cardinality of the H-matching, i.e., the number of disjoint subgraphs $G_i$.

  
  

• Good News: Approximable within $\vert V_H\vert /2+\varepsilon$ for any $\varepsilon >0$ [265].
• Bad News: APX-hard [283].
• Comment: Also called Maximum H-Packing. Transformation from bounded MAXIMUM 3-SATISFIABILITY. The weighted version can be approximated within $2 (\vert V_H\vert+1)/3$ [98]. Variation in which the degree of G is bounded by a constant B is APX-complete [283]. Admits a PTAS for planar graphs [53], but does not admit an FPTAS [73]. Admits a PTAS for $\lambda$-precision unit disk graphs [264]. The case when H is the path with three edges is approximable within 4/3, even in the edge-weighted case [238]. Induced MAXIMUM H-MATCHING, i.e., where the subgraphs $G_i$ are induced subgraphs of G, has the same good and bad news as the ordinary problem, even when the degree of G is bounded. MAXIMUM MATCHING OF CONSISTENT K-CLIQUES is the variation in which H is a k-clique and the vertices of G are partitioned into k independent sets $V_1,\ldots,V_k$, each $V_i$ is partitioned into some sets $V_{i,j}$, and at most one vertex in each $V_{i,j}$ may be included in the matching. This problem is not in APX for $k\ge 5$ and is not approximable within 4/3 for $k\in\{2,3,4\}$. It is not in APX for any $k\ge 2$ unless NP$\subset$QP [457].
• Garey and Johnson: GT12