# Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which has at least one incoming and one outgoing edges for each non-source-non-sink vertex.

Is there a more commonplace formulation of such a problem? Or a reduction to another common problem (minimum spanning tree)? And do efficient algorithms exist?

This seems related to the "Bounded Degree Maximum Spanning Subgraph" problem, but in my case I have a lower bound on a directed graph.

• Hmmm.. Do you want this spanning subgraph to be somehow connected ? – Nathann Cohen Mar 4 '13 at 13:32
• Yes. I figured this was implied by the one incoming, one outgoing, except one source and one sink condition. – Alec Jacobson Mar 5 '13 at 10:12

Let $D$ be the acyclic digraph and let $\pi(D)$ be the minimal number of such paths. So there is a set of disjoint directed paths $P_1,\dots,P_{\pi(D)}$ spanning $D$. Now we add to the starting node of each path (except the one with the source as the starting node) an in-arc and an out-arc to the ending node of each path (except the one eith the sink as the ending node). Then we got a subdigraph with all nodes (except the source and the sink) having at least one arc entering and at least one arc leaving it. This digraph has $|V(D)|+\pi(D) -2$ arcs: each path P_i has $|V(P_i)|-1$ arcs and we added $2(\pi(D)-1)$.
On the other hand lets suppose that we have an acyclic digraph $D'$ with only one source $s$ and only one sink $t$ and all other nodes have both in-degree and out-degree at least 1. In such a graph all "inner nodes" (not source or sink) are on a directed $s-t$ path. Now using the same constructive logic as in building and ear-decomposition we can prove the other direction (I am too lazy to be precise here but if you don't see than I will write down more precisly).
So these two questions are pratically the same. In the case of acyclic graph the $\pi(D)$ can be computed by various means (with LP, with min cost flow, with matroid intersection theorem) but I think the simplest way is with matchings. Suppose $D=(V,A)$ is an acyclic digraph with $V(D)=\{v_1,\dots,v_n\}$. You make a bipartite graph $G=(A\cup B, E)$ where $A=\{v_1',\dots,v_n'\}, B=\{v_1'',\dots,v_n''\}$ and $(v_i'v_j'')\in E~ iff~(v_iv_j)\in A$. Another exercise not to hard to think through (but tiresome to write down) is that a maximum matching in $G$ correspond to an optimal path spanning in $D$.