3
$\begingroup$

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)\}$).

Thanks for your help!

Improve this question
$\endgroup$
2
  • $\begingroup$ Please ask only one question per post. I see two different questions here. I suggest that you ask them separately, by editing the second one out of this post, and asking a new question with the second question. $\endgroup$
    – D.W.
    Jun 26 at 21:52
  • $\begingroup$ Edited the question! $\endgroup$
    – Marco Pegoraro
    Jun 27 at 7:37

1 Answer 1

Reset to default
4
$\begingroup$

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.

For the second (now deleted) problem, the answer is exactly a longest path, by the same argument (assuming you still want the not-quite-matching to be included in a path; this was not clear from the decription).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I feel a bit silly for not realizing this. Thank you for your answer! $\endgroup$
    – Marco Pegoraro
    Jun 27 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.