# The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions

Preprint · Yonghwan Kim, Yuichi Sudo

- Archive id: arxiv:2609.07253
- Published: 2026-09-07
- arXiv: https://arxiv.org/abs/2609.07253
- Source URL: https://arxiv.org/abs/2609.07253
- PDF: https://arxiv.org/pdf/2609.07253
- Provenance: arxiv

## 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)$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.