Integer Programming Approaches to Two Domination Related Problems in Graph Theory

Çınar Arı

We propose integer programming-based solution approaches to two domination-related problems in graph theory. The first one is the Minimum Weighted Paired Dominating Set Problem, where the goal is to find a dominating set whose induced subgraph has a perfect matching, minimizing the total weight of the selected vertices and edges. We propose new integer programming formulations, initiate the study of the paired dominating set polytope, and introduce valid inequalities to strengthen the model. The second one is the Minimum Weighted k-Defensive Dominating Set Problem for which we present an integer programming formulation and propose a row generation method to address the exponential number of constraints in the formulation. We also describe valid inequalities and report some computational results on random graphs. This is a joint work with Mustafa Kemal Tural.

Short Bio

Çınar Arı graduated from the Industrial Engineering Department of Middle East Technical University. He is currently an M.S. student in the same department. He is broadly interested in discrete and combinatorial optimization.

Venue

Friday, April 11th , 2025, 4:00 pm IE Building, Halim Doğrusöz Auditorium (Ground Floor-03)