Efficient domination problem: a quantum computing approach
摘要
Given a graph G(V, E), a dominating set D is a subset of V in which every vertex not in D is adjacent to at least one vertex in D. The concept of Efficient Domination (ED) introduces a variation of domination in a graph, ensuring that every vertex is dominated by exactly one vertex from the dominating set. This concept has been extended to Bi-Efficient Domination (BED), where each vertex is dominated by exactly two vertices in the dominating set. This paper presents a QUBO formulation for the efficient domination problem and transforms it into a Hamiltonian that is well-suited for quantum computing. The approach leverages the Quantum Approximate Optimization Algorithm (QAOA) to solve the problem. Additionally, the paper presents the results of a similar quantum-based approach applied to the bi-efficient domination problem, showcasing the effectiveness of quantum techniques. By bridging graph theory and quantum computing, this work provides a foundation for leveraging quantum algorithms to solve complex domination problems.