The partial domination problem generalizes classic domination by requiring that a specified fraction \(p \in (0, 1]\) of vertices be dominated. The problem is NP-hard on general graphs, and Case et al. (2017) explicitly posed the question of whether the p-domination number \(\gamma _p(T)\) is polynomial-time computable on trees. A polynomial-time algorithm in fact follows from the maximum-coverage work of Blair et al. (2008) on trees, via the threshold reduction \(\gamma _p(T) = \min \{\ell : d(\ell , T) \ge \lceil p|V(T)|\rceil \}\) , a connection that does not appear to have been observed in the partial-domination literature. In this paper we present a direct dynamic programming algorithm for \(\gamma _p(T)\) , formulated in the language of partial domination and built on max-plus convolution. We prove correctness by induction on subtree height, establish a worst-case time complexity of \(O(|V|^2)\) , and give a pruning rule that yields \(O(p \cdot |V|^2)\) , beneficial for small p.
