Skip to main content
2 of 3
added 480 characters in body
usul
  • 4.5k
  • 27
  • 30

I think we can use a greedy-type algorithm based on topological sorting into layers. Due to Tony's answer, we know we can ignore the no-shortcuts assumption, so take any DAG with in-degree and out-degree both bounded by $2$.

Algorithm:

  1. Topologically sort the graph into layers: Let $L_0$ be all vertices with in-degree $0$, and for $j \geq 1$, let $L_j$ be all vertices that are not in $L_0,\dots,L_{j-1}$ and have an in-edge from some vertex in $L_{j-1}$.

  2. Find a maximal matching between $L_0$ and $L_1$.

  3. Find a maximal matching between [the remaining vertices of $L_1$] and $L_2$.

  4. Repeat for each sequential pair of layers $j,j+1$.

Analysis: It helps to re-write the algorithm as follows. First delete from the graph all vertices with no edges. Now find a maximal matching between $L_0$ and $L_1$. Now delete from the graph all vertices in $L_0$, all matched vertices in $L_1$, and all edges incident to any deleted vertex. Repeat this entire process (note that the surviving vertices in $L_1$ become the "new" $L_0$ after the deletions) until the graph is empty.

Note that this process eventually deletes all edges in the graph. We just have to show that at each round, at least $1/4$ the deleted edges are in the matching.

Fix a round and suppose that $k$ edges were matched between $L_0$ and $L_1$. The deleted edges are exactly: (a) all edges between $L_0$ and $L_1$ plus (b) all out-edges from the matched vertices in $L_1$. The set (b) has size at most $2k$, as there are $k$ matched vertices in $L_1$ and each has at most $2$ out-edges. The key claim is that the set (a) also has size at most $2k$, or in other words, at least half of the edges between $L_0$ and $L_1$ are in the matching.

Proof of key claim: Consider just the (undirected) bipartite graph between $L_0$ and $L_1$. Note all vertices have degree either $1$ or $2$. Take any $v$ with degree only $1$ and consider a maximal simple path starting at $v$. This path contains all the edges incident to all vertices on the path. At least half of the edges are in the matching by maximality (else we have an augmenting path). Find another vertex of degree $1$ and maximal simple path, etc. until no more vertices of degree $1$ remain. This decomposes the bipartite graph into disjoint paths of the above form and a "remaninder": a set of vertices all having degree exactly $2$. There must be the same number of vertices from $L_0$ and $L_1$ and they must have a perfect matching, e.g. because they are a disjoint union of even-length cycles, and the total number of edges is exactly twice the number of vertices, so exactly half the edges in this "remainder" are matched.

P.S. Here is a graph where the bound is tight: $L_0$ has $n$ vertices, $L_1$ has $n/2$ vertices, and $L_2$ has $n/2$ vertices. Each vertex in $L_0$ has out-degree $1$, each vertex in $L_1$ has in-degree $2$ and out-degree $2$, each vertex in $L_2$ has in-degree $2$. There are $2n$ edges in the graph, and a maximum matching cannot do better than including all $n/2$ vertices in $L_1$ (since there are no edges between $L_0$ and $L_2$), so any maximum matching has size $n/2$.

usul
  • 4.5k
  • 27
  • 30