  Given a directed graph $G$ on $n$ vertices with a special vertex $s$, the
directed minimum degree spanning tree problem requires computing a incoming
spanning tree rooted at $s$ whose maximum tree in-degree is the smallest among
all such trees. The problem is known to be NP-hard, since it generalizes the
Hamiltonian path problem. The best LP-based polynomial time algorithm can
achieve an approximation of $\Delta^*+2$ [Bansal et al, 2009], where $\Delta^*$
denotes the optimal maximum tree in-degree. As for purely combinatorial
algorithms (algorithms that do not use LP), the best approximation is
$O(\Delta^*+\log n)$ [Krishnan and Raghavachari, 2001] but the running time is
quasi-polynomial. In this paper, we focus on purely combinatorial algorithms
and try to bridge the gap between LP-based approaches and purely combinatorial
approaches. As a result, we propose a purely combinatorial polynomial time
algorithm that also achieves an $O(\Delta^* + \log n)$ approximation. Then we
improve this algorithm to obtain a $(1+\epsilon)\Delta^* + O(\frac{\log
n}{\log\log n})$ for any constant $0<\epsilon<1$ approximation in polynomial
time.

Data Structures and Algorithms