On the complexity of color-avoiding site and bond percolation
arXiv:1810.08484 · doi:10.1007/978-3-030-10801-4_28
Abstract
The mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or edges are not independent but certain classes of vertices or edges share a mutual vulnerability. In this study, we consider a graph and we assign colors to the vertices or edges, where the color-classes correspond to the shared vulnerabilities. An important problem is to find robustly connected vertex sets: nodes that remain connected to each other by paths providing any type of error (i.e. erasing any vertices or edges of the given color). This is also known as color-avoiding percolation. In this paper, we study various possible modeling approaches of shared vulnerabilities, we analyze the computational complexity of finding the robustly (color-avoiding) connected components. We find that the presented approaches differ significantly regarding their complexity.
arXiv comment14 pages
References in corpus (10)
- Error and attack tolerance of complex networks
- Network robustness and fragility: Percolation on random graphs
- k-core organization of complex networks
- Percolation Theory on Interdependent Networks Based on Epidemic Spreading
- Percolation of localized attack on complex networks
- -core percolation on complex networks: Comparing random, localized and targeted attacks
- The maximum disjoint paths problem on multi-relations social networks
- Color-avoiding percolation
- Bond and site color-avoiding percolation in scale free networks
- Critical field-exponents for secure message-passing in modular networks