Cost-Based Variants of Double Roman Domination: Theoretical and Algorithmic Analysis

Standard models for Double Roman domination (DRD) prioritize unit count minimization, often overlooking the financial and operational realities of service allocation. This research examines two separate cost-based generalizations of DRD to identify how different expenses influence optimal network design. By analyzing costs at both the vertex and edge levels, we provide a broader understanding of resource allocation than traditional models based strictly on cardinality.

For Minimum Cost DRD, weights are assigned to vertices representing location-specific hosting expenses. This problem is addressed through dynamic programming for tree structures and a heuristic based on greedy construction and a local search for general graphs. Separately, we investigate Edge Cost DRD, which models the effort or risk of moving units between nodes. For this variant, we analyze two operational priorities, Sum Cost and Worst Case, and develop polynomial time algorithms for solving each on tree structures.

Our analysis establishes that both generalizations remain NP-hard on general graphs, yet are solvable in linear or polynomial time on tree structures. Experimental evaluations for the Minimum Cost variant confirm that the proposed heuristic provides high-quality solutions for general networks. Regarding Edge Cost DRD, a significant structural property is established for the Worst Case priority, proving the existence of an optimal solution where no vertex is assigned a value of one.

By presenting these two perspectives, this research clarifies the trade-offs between fixed deployment expenses and operational movement costs. This comparative analysis offers a rigorous foundation for disaster response and logistics, where both resource location and mobility are essential. These results demonstrate that accounting for different cost dimensions is critical for moving domination theory toward practical application in heterogeneous environments.