Next: MINIMUM BOTTLENECK PATH MATCHING Up: Covering and Partitioning Previous: MAXIMUM TRIANGLE PACKING Index

### MAXIMUM H-MATCHING

- INSTANCE: Graph and a fixed graph with at least three vertices in some connected component.

- SOLUTION: A H-matching for G, i.e., a collection of disjoint subgraphs of G, each isomorphic to H.

- MEASURE: Cardinality of the H-matching, i.e., the number of disjoint subgraphs Gi.

- Good News: Approximable within for any [250].

- Bad News: APX-hard [268].

- Comment: Also called Maximum H-Packing. Transformation from bounded MAXIMUM 3-SATISFIABILITY. The weighted version can be approximated within 2 (|VH|+1)/3 [90]. Variation in which the degree of G is bounded by a constant B is APX-complete [268]. Admits a PTAS for planar graphs [50], but does not admit an FPTAS [68]. Admits a PTAS for -precision unit disk graphs [249].

  The case when H is the path with three edges is approximable within 4/3, even in the edge-weighted case [221].

  Node-disjoint paths with three edges each.

- MEASURE: Total weight of the edges of the paths.

  Induced MAXIMUM H-MATCHING, i.e., where the subgraphs Gi 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 , each Vi is partitioned into some sets Vi,j, and at most one vertex in each Vi,j may be included in the matching. This problem is not in APX for and is not approximable within 4/3 for . It is not in APX for any unless NPQP [434].

- Garey and Johnson: GT12

Next: MINIMUM BOTTLENECK PATH MATCHING Up: Covering and Partitioning Previous: MAXIMUM TRIANGLE PACKING Index