Summary
Figuring out large sets of points in a network where each pair can 'see' each other without getting blocked is usually very hard. The researchers focused on cactus graphs, a special kind of network with simple cycle structures, where this problem was still unsolved. They found the maximum size of these mutually visible sets for cactus graphs and developed algorithms that can reliably build such sets even if the system starts in a mixed-up state. These algorithms operate efficiently, relying on network tree structures and distance properties, and the researchers also proved that their second algorithm is as fast as possible based on certain graph characteristics.
graph theorymutual visibility setcactus graphshortest pathself-stabilizing algorithmBFS treeNP-completedistributed computingtreewidthgraph algorithm
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)$.