The h-Hop Dominating Subnetwork Problem: Variants, Structural Properties, and Exact Solution Approaches

This paper introduces the h-hop dominating subnetwork problem (HSDP), a graph-optimization problem that jointly selects a prescribed number of operational vertices, determines the dominant vertices within the selected set, and assigns each selected vertex to a dominant within a given hop range. Unlike classical domination models, the set of vertices subject to domination is therefore determined endogenously. A unified mixed-integer linear programming framework is developed to incorporate capacity and internal connectivity requirements, structural properties, and capacity-based bounds. For the connected variants, two established exact connectivity-enforcement mechanisms, a single-commodity flow formulation and a branch-and-cut implementation with dynamically generated connectivity constraints, are applied and compared. Computational experiments on random geometric graphs illustrate the effects of the main design requirements and show that the relative performance of the two connectivity implementations depends on the tested instance characteristics. The results demonstrate the modeling flexibility of the HSDP framework and identify scalability and graph-topology dependence as relevant directions for further study.