Maximum mutual visibility sets found and built on cactus graphs
The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions
Distributed, Parallel, and Cluster ComputingDiscrete MathematicsData Structures and Algorithms
Summary
The paper studies a way to pick special points (vertices) on a network (graph) so that each pair can see each other clearly along shortest paths. Finding the largest such set is known to be very hard for general graphs. The authors focus on cactus graphs, a simpler kind of network, and figure out the exact size of the largest set. They also provide two algorithms that can run independently and eventually build these sets automatically in a distributed way.
What this means in practice
- •For network engineers: Design distributed protocols that maintain maximum mutual visibility sets to ensure efficient communication over cactus-like network topologies.
- •For distributed systems developers: Implement self-stabilizing algorithms to automatically recover and maintain key network structures in dynamic or unreliable environments modeled by cactus graphs.
Authors
Yonghwan Kim, Yuichi Sudo
Abstract
Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are \emph{mutually visible} if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a \emph{Mutual Visibility Set} (\MVS) if every pair of vertices in $S$ is mutually visible. The concept of \MVS s in graphs has attracted significant attention since its introduction, as it provides an important structural property of graphs. However, determining a maximum \MVS\ in general graphs is computationally intractable; the decision problem of whether a graph admits an \MVS\ of size at least $k$ has been shown to be \emph{NP-complete}. Thus, prior work has focused on finding maximal \MVS s or restricting attention to specific graph classes. Cactus graphs form a fundamental low-treewidth class, yet the maximum \MVS\ problem for this class remains open. In this paper, we first determine the size of maximum \MVS~in cactus graphs, and introduce two self-stabilizing algorithms that construct such sets. The first algorithm uses a single BFS tree and stabilizes in $O(D)$ rounds with $O(\log n)$ bits per process on average; the second one uses parallel BFS trees and stabilizes in $O(|C_{\max}|+|T_{\max}|)$ rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where $|C_{\max}|+|T_{\max}| = o(D)$.