A Polynomial-Time Algorithm for Partial Domination in Trees

The partial domination problem generalizes classic domination by requiring that a specified fraction p ∈ (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 γ ₚ(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 γ ₚ(T) = min \ : d( , T) ≥ p|V(T)| \ , 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 γ ₚ(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|²) , and give a pruning rule that yields O(p · |V|²) , beneficial for small p.