Abstract: The Double Roman Domination Problem (DRDP) is an NP-hard combinatorial optimization problem that is a variant of the classical graph domination problem. This thesis develops four greedy heuristics for solving the DRDP: Vertex Cover Based Construction (built on star graph decomposition), Sum of Nth-Degree Based Heuristics (a weighted and a concentration variant), Maximal Biclique Decomposition, and Gain-Factor Based Construction. Each uses a different vertex-scoring strategy to construct low-weight double Roman dominating functions. The thesis also adapts several metaheuristic and hyper-heuristic frameworks to the DRDP for the first time: Simulated Annealing, GRASP-Lite, and Entropy-Guided Ruin-and-Recreate as metaheuristics, and a Contextual Bandit Hyper-heuristic.The evaluation compares these methods against existing baselines from earlier work for solving the DRDP: naive Degree-Greedy construction, Ant Colony Optimization, and a Genetic Algorithm. The benchmark contains path and cycle graphs with known optimal values, synthetic Erdős–Rényi random graphs of varying density, and real-world sparse matrices from the Harwell-Boeing collection. Across the full 143-graph benchmark, Simulated Annealing metaheuristic achieves the lowest mean rank (2.02) and the most best-or-tied scores (113). The Contextual Bandit Hyper-heuristic ranks second (3.15), and Ant Colony Optimization ranks third (3.86). In the subset of real-world Harwell-Boeing graphs, after Simulated Annealing, Ant Colony Optimization comes second and Contextual Bandit Hyper-heuristic comes third. Genetic Algorithm comes fourth in both cases. Gain-Factor Based Construction scores below these methods, but it runs much faster. This makes Gain-Factor Based Construction a fast baseline for heavier metaheuristic and Hyper-heuristic constructions. These findings will improve the understanding of solving DRDP, with applications in domains such as network monitoring, facility and resource placement, and wireless sensor network deployment.

 

Presenter: Samidhya Sarker (Std No. 1018052049)

Venue: Graduate Seminar Room