  A rainbow matching in an edge-colored graph is a matching whose edges have
distinct colors. We address the complexity issue of the following problem,
\mrbm: Given an edge-colored graph $G$, how large is the largest rainbow
matching in $G$? We present several sharp contrasts in the complexity of this
problem.
  We show, among others, that
  * can be approximated by a polynomial algorithm with approximation ratio
$2/3-\eps$. * is APX-complete, even when restricted to properly edge-colored
linear forests without a $5$-vertex path, and is solvable in %time $O(m^{3/2})$
on edge-colored $m$-edge polynomial time for edge-colored forests without a
$4$-vertex path. * is APX-complete, even when restricted to properly
edge-colored trees without an $8$-vertex path, and is solvable in %time
$O(n^{7/2})$ on edge-colored $n$-vertex polynomial time for edge-colored trees
without a $7$-vertex path. * is APX-complete, even when restricted to properly
edge-colored paths.
  These results provide a dichotomy theorem for the complexity of the problem
on forests and trees in terms of forbidding paths. The latter is somewhat
surprising, since, to the best of our knowledge, no (unweighted) graph problem
prior to our result is known to be NP-hard for simple paths. We also address
the parameterized complexity of the problem.
