Two Approaches to Constructing Certified Dominating Sets in Social Networks

Abstract

Social networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civilian, to prevent potential abuses. To delve deeper into this topic, this study considers two approaches to the problem of finding certified dominating sets of small cardinality. One approach is to transform an ordinary dominating set, which is subject only to condition 1) given above, into a certified dominating set. The second approach involves constructing such a set from scratch. To compare the two methods, we first studied the computational complexity of the decision problem of whether, for a given graph, the domination number, which is the minimum size of a dominating set, is equal to the certified domination number, that is, the minimum size of a certified dominating set. Next, we constructed and compared the performance of two approximate algorithms that find certified dominating sets, one for each of the two approaches. The effectiveness and efficiency of the proposed algorithms were validated through experiments that compare their results with each other and with a previous study: the linear-time algorithm, which determines the certified domination number for trees and with known results for the domination number in social networks.

Keywords

• Algorithmic efficiency
• approximation algorithms
• certified domination number
• computational complexity
• domination number
• safety