QUBO Modeling for a Spectrum of Domination Problems

As quantum computing advances, the application of quantum algorithms to address combinatorial optimization problems on quantum computers has emerged as a pivotal area of research. The quadratic unconstrained binary optimization (QUBO) acts as an intermediary, facilitating the translation of combinatorial optimization problems into a quantum computing context, thereby constituting an essential foundation for this field of inquiry. Within the realm of combinatorial optimization, the domination problem (DP) is pertinent to a myriad of real-world applications, including, but not limited to, the strategic placement of fire stations and the analysis of social network structures. Furthermore, the DP encompasses a multitude of variants, exemplified by the independent DP, total DP, and k-domination, among others. However, a dearth of research exists within the quantum computing community regarding these variant problems. One plausible explanation for this gap is the absence of comprehensive QUBO modeling research pertaining to these issues. This paper delves into the methodologies of QUBO modeling for both the canonical DP and its diverse variants. For the classic DP, we have refined the existing QUBO modeling methods, addressing the issue of incomplete modeling. Additionally, we have optimized the variable representation of the slack terms in the penalty items of DP. At the same time, we introduce novel QUBO modeling methods for a spectrum of DP variants, marking a pioneering effort in this domain. Our contributions are anticipated to expedite the integration of DP into the burgeoning quantum computing landscape.