Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  mangledorf Mar 5 '13 at 10:12
add comment

1 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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.