A Polynomial-Time Algorithm for Partial Domination in Trees

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.