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.
Best Answer
It is essentally the same question as to which is the minimum number of disjoint directed paths spanning the digraph (or covering all the vertices in other words).
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$.