Maximum matching in a graph with no "shortcuts"

Question

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).

An arc $(u,v)$ in $G$ is called a shortcut if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.

In our research, we came up with the following conjecture:

Conjecture. Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.

Small examples seem to support this conjecture, although a general proof appears quite elusive. The lower bound $\frac{1}{5}e(G)$ here is almost trivial (and holds even with shortcuts), and with some effort we were able to prove the bound $\frac{2}{9}e(G)$.

Any help in proving or disproving the conjecture will be appreciated.

P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.

Answer 1

Yes, your conjecture is true, even without the assumption that $G$ does not contain shortcuts. The following proof is due to Sam Fiorini.

Proof. Let $P \subseteq \mathbb{R}^{E(G^\star)}$ be the matching polytope of $G^\star$. That is, $P$ is the convex hull of the set of characteristic vectors of matchings of $G^\star$. By Edmonds' matching polytope theorem, $P$ consists of all $x \in \mathbb{R}_{\geq 0}^{E(G^\star)}$ such that

$\sum_{e \in \delta(v)} x_e \leq 1$, for all $v \in V(G^\star)$

and

$\sum_{e \in E(S)} x_e \leq \frac{|S|-1}{2}$, for all odd $S \subseteq V(G^\star)$.

Here $\delta(v)$ is the set of all edges incident to $v$, and $E(S)$ is the set of edges with both endpoints in $S$.

Now, let $x^*$ be the vector such that $x_e^*=\frac{1}{4}$, for all $e\in E(G^\star)$. We show that $x^*$ is in the matching polytope. Clearly, $x^*$ satisfies the first type of constraints, since $G^\star$ has maximum degree $4$.

For the second type of constraints, let $S \subseteq V(G)$ with $|S| \geq 3$ and odd. Since $G$ is acyclic, $G[S]$ contains a source and a sink vertex. Thus, $H:=G^\star[S]$ contains two distinct vertices of degree at most $2$. All other vertices of $H$ have maximum degree $4$, thus

$$ \sum_{e \in E(S)} x^*_e =|E(S)|/4 =\sum_{v \in S} \deg_H(v)/8 \leq (|S|-1)/2. $$

Thus, the vector $x^*$ can be written as a convex combination of matchings, which in particular implies that there must be a matching of size at least $e(G)/4$.

Answer 2

We may use Tutte maximal matching theorem (in Berge's form) instead of Edmonds matching polytope theorem, as in the proof by Sam Fiorini provided by Tony Huynh.

Denote by $n, m$ the number of vertices and arcs respectively. Let a maximal matching cover all vertices but $t$, that is, its size equals $(n-t)/2$. Then, by Tutte--Berge there exists a set $S$ of vertices such that $G^\ast-S$ has at least $|S|+t$ components $C_1,\ldots,C_{k}$, $k\geqslant |S|+t$ (there exist $|S|+t$ odd components, but we only need so many non-empty components.) Each component $C_i$ contains a vertex $v_i$ from which there is no arc inside $C_i$ (otherwise we have a cycle). All arcs from $v_1,\ldots,v_k$ go to $S$, and since indegrees in $S$ do not exceed 2, we conclude that there exist at most $2|S|$ arcs going from $v_i$'s, and at most $2$ arcs from each of $n-k$ other vertices, in total at most $2(n-k+|S|)\le 2(n-t)$ arcs. Thus, $m/4\leqslant (n-t)/2$, as needed.

Answer 3

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: For any $n \geq 4$, $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 every edge has an endpoint in $L_1$), so any maximum matching has size $n/2$.