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.
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
NP
QP [434].