2009/04/15 by Ching-Lueh Chang, Chang, Ching-Lueh, Yuh-Dauh Lyuu +2 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Game Theory and Applications #Parallel #Stochastic processes and statistical mechanics #and Cluster Computing (cs.DC) #cs.DC #cs.DM
paper · pdf · doi:10.48550/arxiv.0904.2306
openalex publication_date 2009/04/15 · arxiv created 2010/03/09 · arxiv updated 2010/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider the following coloring process in a simple directed graph G(V,E) with positive indegrees. Initially, a set S of vertices are white, whereas all the others are black. Thereafter, a black vertex is colored white whenever more than half of its in-neighbors are white. The coloring process ends when no additional vertices can be colored white. If all vertices end up white, we call S an irreversible dynamic monopoly (or dynamo for short) under the strict-majority scenario. An irreversible dynamo under the simple-majority scenario is defined similarly except that a black vertex is colored white when at least half of its in-neighbors are white. We derive upper bounds of (2/3) | V | and | V |/2 on the minimum sizes of irreversible dynamos under the strict and the simple-majority scenarios, respectively. For the special case when G is an undirected connected graph, we prove the existence of an irreversible dynamo with size at most \lceil | V |/2 \rceil under the strict-majority scenario. Let ε>0 be any constant. We also show that, unless NP⊆ TIME(nO(ln ln n)), no polynomial-time, ((1/2-ε)ln | V |)-approximation algorithms exist for finding the minimum irreversible dynamo under either the strict or the simple-majority scenario. The inapproximability results hold even for bipartite graphs with diameter at most 8.