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 DD and a nonnegative integer kk, the goal is to construct a spanning out-tree TT of DD such that at least kk vertices in TT have the same out-degree as in DD. 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 TT such that at most kk vertices in TT have out-degrees that are different from that in DD. We show that this problem is fixed-parameter tractable and that it admits a problem kernel with at most 8k8k vertices on strongly connected digraphs and O(k2)O(k2) vertices on general digraphs. We also give an algorithm for this problem on general digraphs with running time O(5.942k⋅nO(1))O(5.942k⋅nO(1)), where nn is the number of vertices in the input digraph.