On the directed Full Degree Spanning Tree problem

We study the parameterized complexity of a directed analog of the Full Degree Spanning Tree problem where, given a digraph $D$ and a nonnegative integer $k$ , the goal is to construct a spanning out‐tree $T$ of $D$ such that at least $k$ vertices in $T$ have the same out‐degree as in $D$ . We show that this problem is W[1]‐hard even on the class of directed acyclic graphs. In the dual version, called Reduced Degree Spanning Tree, one is required to construct a spanning out‐tree $T$ such that at most $k$ vertices in $T$ have out‐degrees that are different from that in $D$ . We show that this problem is fixed‐parameter tractable and that it admits a problem kernel with at most $8k$ vertices on strongly connected digraphs and $O\left(k^2\right)$ vertices on general digraphs. We also give an algorithm for this problem on general digraphs with running time $O(5.942^k·n^{O\left(1\right)})$ , where $n$ is the number of vertices in the input digraph.