Abstract
Consider the following process on a simple undirected connected graph \( {\text{G}}\left( {V,E} \right) \). At the beginning, only a set S of vertices are active. Subsequently, a vertex is activated if at least an \( \alpha \in \left( {0,1} \right) \) fraction of its neighbors are active. The process stops only when no more vertices can be activated. Following earlier papers, we call S an α perfect target set, abbreviated α-PTS, if all vertices are activated at the end. Chang [1] proposes a randomized polynomial-time algorithm for finding an α-PTS of expected size \( (2\sqrt 2 + 3)\left\lceil {\alpha |{\text{V}}|} \right\rceil \), where the expectation is taken over the random coin tosses of the algorithm. We note briefly that the method of conditional expectation can be used to derandomize Chang’s algorithm. So the derandomized algorithm finds an α-PTS of size no more than \( (2\sqrt 2 + 3)\left\lceil {\alpha |{\text{V}}|} \right\rceil \) given any simple undirected connected graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chang, C. -L. (2011). Triggering cascades on undirected connected graphs. Information Processing Letters, 11(19), 973–978.
Peleg, D. (2002). Local majorities, coalitions and monopolies in graphs: A review. Theoretical Computer Science, 282(2), 231–257.
Flocchini, P., Geurts, F., & Santoro, N. (2001). Optimal irreversible dynamos in chordal rings. Discrete Applied Mathematics, 113(1), 23–42.
Flocchini, P., Královic, R., Ruzicka, P., Roncato, A., & Santoro, N. (2003). On time versus size for monotone dynamic monopolies in regular topologies. Journal of Discrete Algorithms, 1(2), 129–150.
Flocchini, P., Lodi, E., Luccio, F., Pagli, L., & Santoro, N. (2004). Dynamic monopolies in tori. Discrete Applied Mathematics, 137(2), 197–212.
Adams, S. S., Troxell, D. S., & Zinnen, S. L. (2011). Dynamic monopolies and feedback vertex sets in hexagonal grids. Computers and Mathematics with Applications, 62(11), 4049–4057.
Chang, C. -L., & Lyuu, Y. -D. (2010). Bounding the number of tolerable faults in majority-based systems. In Proceedings of the 7th International Conference on Algorithms and Complexity (pp. 109–119). Rome, Italy.
Ackerman, E., Ben-Zwi, O., & Wolfovitz, G. (2010). Combinatorial model and bounds for target set selection. Theoretical Computer Science, 411(44–46), 4017–4022.
Khoshkhah, K., Soltani, H., & Zaker, M. (2012). On dynamic monopolies of graphs: The average and strict majority thresholds. Discrete Optimization, 9(2), 77–83.
Chen, N. (2008). On the approximability of influence in social networks. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Mathematics (pp. 1029–1037).
Dreyer, P. A., & Roberts, F. S. (2009). Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7), 1615–1627.
Kempe, D. Kleinberg, J, & Tardos, E. (2003). Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 137–146).
Kralovic, R. (2001). On majority voting games in trees. In Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics (pp. 282–291.
Gleeson, J. P., & Cahalane, D. J. (2002). Seed size strongly affects cascades on random networks. Physical Review E, 75(5), 056103.
Watts, D. J. (2002). A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences 99(9), 5766–5771.
Berger, E. (2001). Dynamic monopolies of constant size. Journal of Combinatorial Theory Series B, 83(2), 191–200.
Goles, E., & Olivos, J. (1980). Periodic behaviour of generalized threshold functions. Discrete Mathematics, 302, 187–189.
Kleinberg, J. (2000). The small-world phenomenon: An algorithm perspective. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (pp. 163–170.
Morris, S. (2000). Contagion. Review of Economic Studies, 67(1), 57–78.
Peleg, D. (1998). Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2–3), 263–273.
Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge: Cambridge University Press.
Acknowledgments
Ching-Lueh Chang is supported in part by the Ministry of Economic Affairs under grant 102-E0616 and the National Science Council under grant 101-2221-E-155-015-MY2.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, YL., Chang, CL. (2014). A Short Note on Derandomization of Perfect Target Set Selection. In: Juang, J., Chen, CY., Yang, CF. (eds) Proceedings of the 2nd International Conference on Intelligent Technologies and Engineering Systems (ICITES2013). Lecture Notes in Electrical Engineering, vol 293. Springer, Cham. https://doi.org/10.1007/978-3-319-04573-3_59
Download citation
DOI: https://doi.org/10.1007/978-3-319-04573-3_59
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04572-6
Online ISBN: 978-3-319-04573-3
eBook Packages: EngineeringEngineering (R0)