On the Constrained Maximization of Influence Over a Directed Tree Structure

Maximizing influence in networks is a widely studied prob- lem with applications across various domains. In this paper, we app- roach this problem by considering influence maximization in directed tree structures. Given a tree T , each node is associated with a binary label, obtaining 1−nodes and 0−nodes. The influence of 1−nodes over T is then computed as the total number of 0−nodes in their neigh- bourhood. Given an integer k, our objective is to identify a subset of k 1−nodes that maximizes the influence over T . After analysing heuristic approaches and their limitations, we present a dynamic programming algorithm for solving this problem exactly when the maximum degree and k are fixed. Our findings provide new insights into influence maxi- mization in directed tree structures and establish a foundation for further exploration of constrained optimization problems.