Dynamic programming algorithms for the conditional covering problem on path and extended star graphs

The Conditional Covering Problem (CCP) is a facility location problem on a graph, where the set of nodes represents demand points and potential facility locations. The key aspect of the CCP is that each facility covers all nodes within a given facility-specific coverage radius, except for the node at which it is located. The objective of this problem is to minimize the sum of the facility location costs required to cover all demand points. We first discuss the worst-case complexity of the CCP by examining literature related to the total domination problem, which is a special case of the CCP. Next, we examine the special case of path graphs and provide an O(n²) algorithm for its solution. Finally, we leverage information obtained from this procedure to derive an optimal algorithm for ‘extended star’ graphs (multiple paths having one node in common), without increasing the worst-case complexity of the algorithm.