On the Directed Degree-Preserving Spanning Tree Problem

Abstract

In this paper we initiate a systematic study of the Reduced Degree Spanning Tree (d -RDST) problem, where given a digraph D and a nonnegative integer k, the goal is to construct a spanning out-tree with at most k vertices of reduced out-degree. We show that this problem is fixed-parameter tractable and admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k²) vertices on general digraphs. We also give an algorithm for this problem on general digraphs with run-time O^*(5.942^k). We also consider the dual of d-RDST: given a digraph D and a nonnegative integer k, construct a spanning out-tree of D with at least k vertices of full out-degree. We show that this problem is W[1]-hard on two important digraph classes: directed acyclic graphs and strongly connected digraphs.