# Maximum cardinality matching on DAGs

A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "touched" at most once) is well-known and studied, and has a easy-to-implement cubic time solution.

Information are very sparse for the case of directed acyclic graphs, however. I am trying to find an entry point in literature for a problem related to maximum matching on DAGs:

Is there any algorithm that, given a DAG, finds the maximum matching that lies on a path? For instance, for the DAG with nodes $$\{x, y, z, w\}$$ and arcs $$\{(x, y), (y, z), (z, w), (x, w)\}$$, the set of arcs $$\{(y, z), (x, w) \}$$ is a maximum cardinality matching. However, it does not lie on a path (the "valid" maximum matching would be, in this case, $$\{(x, y), (z, w)\}$$).

A matching that lies on a path of length (number of edges) $$m$$ has at most $$m+1$$ vertices, and therefore at most $$\lceil m/2\rceil$$ edges; conversely, such a path does include a matching with $$\lceil m/2\rceil$$ edges, namely the one obtained by taking every other edge of the path. Thus, in order to find a maximum matching on a path, it is enough to find a longest path, and this can be done in linear time (in a unit-cost RAM model) by straightforward dynamic programming, see e.g. Wikipedia.