소비자 네트워크의 변화 관리 문제 : 최소지배집합 역 문제의 계산 복잡성 증명

Customer networks go through constant changes. They may expand or shrink once they are formed. In dynamicenvironments, it is a critical corporate challenge to identify and manage influential customer groups in a cost effectiveway. In this context, we apply inverse optimization theory to suggest an efficient method to manage customer networks. In this paper, we assume that there exists a subset of nodes that might have a large effect on the network andthat the network can be modified via some strategic actions. Rather than making efforts to find influential nodes wheneverthe network changes, we focus on a subset of selective nodes and perturb as little as possible the interactionbetween nodes in order to make the selected nodes influential in the given network. We define the following problembased on the inverse optimization. Given a graph and a prescribed node subset, the objective is to modify the structureof the given graph so that the fixed subset of nodes becomes a minimum dominating set in the modified graph andthe cost for modification is minimum under a fixed norm. We call this problem the inverse dominating set problemand investigate its computational complexity.