<p>A matching that lies on a path of length (number of edges) <span class="math-container">$m$</span> has at most <span class="math-container">$m+1$</span> vertices, and therefore at most <span class="math-container">$\lceil m/2\rceil$</span> edges; conversely, such a path does include a matching with <span class="math-container">$\lceil m/2\rceil$</span> 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. <a href="https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs" rel="nofollow noreferrer">Wikipedia</a>.</p>
<p>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).</p>

CC BY-SA 4.0
2023-06-27T12:50:09.333Z
I feel a bit silly for not realizing this. Thank you for your answer!
Marco Pegoraro
CC BY-SA 4.0
2023-06-27T09:11:05.423Z
2023-06-27T09:29:11.657Z
2023-06-27T09:29:11.657Z
Emil Jeřábek
<p>A question on computational complexity and graph theory. The problem of finding <strong>maximum cardinality matchings</strong> of undirected graphs (the largest selection of edges such that each vertex is &quot;touched&quot; at most once) is well-known and studied, and has a easy-to-implement cubic time solution.</p>
<p>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 <strong>DAGs</strong>:</p>
<p>Is there any algorithm that, given a DAG, finds the maximum matching that <strong>lies on a path</strong>? For instance, for the DAG with nodes <span class="math-container">$\{x, y, z, w\}$</span> and arcs <span class="math-container">$\{(x, y), (y, z), (z, w), (x, w)\}$</span>, the set of arcs <span class="math-container">$\{(y, z), (x, w) \}$</span> is a maximum cardinality matching. However, it does not lie on a path (the &quot;valid&quot; maximum matching would be, in this case, <span class="math-container">$\{(x, y), (z, w)\}$</span>).</p>
<p>Thanks for your help!</p>

CC BY-SA 4.0
2023-06-26T21:52:39.593Z
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.
D.W.
CC BY-SA 4.0
2023-06-27T07:37:09.513Z
Edited the question!
Marco Pegoraro
<graph-theory><graph-algorithms><matching>
Maximum cardinality matching on DAGs
Marco Pegoraro
# Maximum cardinality matching on DAGs

(Asked by: username_0 on 2023-06-26)

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!

**Tags:** graph-theory, graph-algorithms, matching
> **Comments:**
> **username_1**: 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.  
> **username_0**: Edited the question!  

---

## 1 answers

### Answer by username_2 on 2023-06-27. Score: 4 | Accepted answer

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](https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs).

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).

> **Comments:**
> **username_0**: I feel a bit silly for not realizing this. Thank you for your answer!  

---

