Quantum Algorithm for the Domatic Number Problem
Andris Ambainis, Ilja Repko · Baltic Journal of Modern Computing · 2024
In this paper we design a quantum algorithm for the NP-complete problem of finding the domatic number.The DOMATIC NUMBER problem asks to determine the largest integer k, such that a given undirected graph with n vertices can be partitioned into k pairwise disjoint dominating sets.This problem finds significant applications, such as in wireless sensor networks, where the selection of multiple dominating sets balances energy consumption and extends network lifetime.Each node communicates exclusively with designated nodes, and dominant sets ensure network resilience by enabling seamless replacement in case of node cluster failure.The importance of this problem lies in its implications for network optimization, highlighting the advantages of quantum computing in addressing complex combinatorial challenges.We present a quantum algorithm that solves this problem in time O(2.4143 n ), which we further improve to O(2.3845 n ).