An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth.

In this paper, we introduce a problem called Minimum subTree problem with Degree Weights , or MTDW. This problem generalized covering tree problems like Spanning Tree , Steiner Tree , Minimum Branch Vertices , Minimum Leaf Spanning Tree , or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V , E) , a set of m + 1 mappings C 1 , C 2 , ... , C m , D : V × N → Z , a set of m integers K 1 , K 2 , ... , K m ∈ Z and a positive integer ℓ , in the search of a forest (T 1 , T 2 , ... , T ℓ) containing ℓ node-disjoint trees of G. Along with K j , the mapping C j defines a constraint that should be satisfied by the trees of the forest. For each tree T i , it associates each node v of V to the score C j (v , d T i (v)) where d T i (v) is the degree of v in T i (possibly 0 if the node is not in T i). The sum ∑ v ∈ V C j (v , d T i (v)) should not exceed K j. In addition, the forest should minimize ∑ i = 1 ℓ ∑ v ∈ V D (v , d T i (v)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m , the value ℓ , the treewidth of the input graph G and Δ, the minimum degree above which all the constraints and D are constant (for every j ∈ 〚 1 , m 〛 , v ∈ V and d ≥ Δ , C j (v , d) = C j (v , Δ) , and D (v , d) = D (v , Δ)). For this problem, we provide a first dichotomy P versus NP -hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1] -hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits , Minimum Branch Vertices , Generalized branch vertices , or k -Bottleneck Steiner Tree. [ABSTRACT FROM AUTHOR]