Fault‐Tolerant Mutual‐Visibility: Complexity and Solutions for Grid‐Like Networks

Abstract

ABSTRACT Networks are often modeled using graphs, and within this setting we introduce the notion of ‐fault‐tolerant mutual visibility. Informally, a set of vertices in a graph is a ‐fault‐tolerant mutual‐visibility set (‐ftmv set) if any two non‐adjacent vertices in are connected by a bundle of shortest paths such that: () each shortest path contains no other vertex of , and () these paths are internally disjoint. The cardinality of a largest ‐ftmv set is denoted by . The classical notion of mutual visibility corresponds to the case . This generalized concept is motivated by applications in communication networks, where agents located at vertices must communicate both efficiently (i.e., via shortest paths) and confidentially (i.e., without messages passing through the location of any other agent). The original notion of mutual visibility may fail in unreliable networks, where vertices or links can become unavailable. Several properties of ‐ftmv sets are established, including a natural relationship between and , as well as a characterization of graphs for which is large. It is shown that computing is NP‐hard for any positive integer , whether is fixed or not. Exact formulae for are derived for several specific graph topologies, including grid‐like networks such as cylinders and tori, and for diameter‐two networks defined by Hamming graphs and by the direct product of complete graphs.

The authors' abstract, as published at the source. Networks, 2026 · DOI ↗