PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yonghwan Kim, Yuichi Sudo

arXiv:2609.07253v1cs.DCcs.DMcs.DS

TL;DR

Cactus graphs are a low-treewidth class whose maximum mutual visibility number had not been determined, despite known results for other graph classes. The paper derives an exact formula and presents two self-stabilizing algorithms for constructing maximum mutual visibility sets, with a tight parameterized stabilization bound for one algorithm.

  • Problem

    The maximum mutual visibility number of cactus graphs had not been determined, despite known results for other graph classes.

    Source: §1 · p. 2

  • Method

    The paper derives a cycle–tree formula for cactus graphs and gives two self-stabilizing maximum-MVS constructions using single-root and parallel BFS trees.

    Source: §1 · p. 2

  • Results

    For cactus graphs, µ(G) = 2n2 + nlt + n1 + ℓ(G), and the two algorithms stabilize in O(D) and O(|Cmax| + |Tmax|) rounds, with the latter bound asymptotically tight.

    Source: §1 · p. 2, §3.5 · p. 13

  • Takeaways & Limitations

    Both algorithms converge to a maximum MVS from any initial configuration under the distributed daemon.

    Source: §1 · p. 2

    A maximum MVS need not attain the capacity bound on every cycle component.

    Source: §3.5 · p. 14

Abstract

from arXiv · show

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

1 Introduction

The paper addresses the undetermined maximum mutual visibility number (MVN) of cactus graphs, a low-treewidth class. It gives an exact formula and two self-stabilizing algorithms for constructing maximum mutual visibility sets.

1 Introduction

  • The paper gives an exact formula for the MVN of cactus graphs, where no exact characterization was previously known.Cactus graphs generalize trees and cycles.Source: §1 · p. 2
  • The formula is µ(G) = 2n2 + nlt + n1 + ℓ(G), using counts of twin-, latent twin-, and unit-cycles and leaves.The paper classifies cycle components using a cycle–tree decomposition.Source: §1 · p. 2
  • A single-root BFS algorithm constructs a maximum MVS and stabilizes in O(D) rounds, using O(log n) bits per process on average.D is the graph diameter.Source: §1 · p. 2
  • A parallel-BFS algorithm stabilizes in O(|Cmax| + |Tmax|) rounds, and this bound is asymptotically tight in those parameters.The algorithm runs BFS trees from high-degree vertices and allows component-wise early termination.Source: §1 · p. 2
  • The paper gives a family where |Cmax| + |Tmax| is an arbitrarily small fraction of D, yet every correct self-stabilizing algorithm requires Ω(|Cmax| + |Tmax|) rounds.This establishes the parameterized lower bound for the parallel-BFS algorithm’s stabilization time.Source: §1 · p. 2
  • Both algorithms converge to a maximum MVS from any initial configuration under the distributed daemon.The full version also develops the algorithms’ rules, complexity analysis, and lower-bound construction.Source: §1 · p. 2

2 Related Work

Prior work established hardness for general graphs and exact MVN results for several graph classes, while cactus graphs remained unresolved. Research also developed self-stabilization models and variants of mutual visibility.

2 Related Work

  • Self-stabilization guarantees convergence from any initial configuration, and the paper works in the classical model under the distributed daemon.For silent algorithms, a prior Ω(log n) memory-per-register lower bound for tasks such as leader election and spanning-tree construction does not transfer to maximum MVS [12].Source: §2 · pp. 2–3
  • The graph-theoretic MVS problem is NP-complete to decide at a target size, and strong inapproximability results are known for graphs of diameter at least three and diameter two.The cited results rule out approximation within n1/3−ε for diameter-at-least-three graphs and establish APX-hardness at diameter two [2].Source: §2 · p. 3
  • Exact MVN formulas or algorithms were known for paths, cycles, block graphs, cographs, grids, and distance-hereditary graphs, but not cactus graphs.Further results address graph products and other graph classes [6, 7, 8, 18, 19].Source: §2 · p. 3
  • Prior work also proposed total, dual, outer, and independent variants of mutual visibility [5, 3].The graph-theoretic formulation was introduced by Di Stefano [21].Source: §2 · p. 3

3 The Mutual Visibility Number on Cactus Graphs

The section determines the mutual visibility number for cactus graphs that are not simple cycles, developing cycle-component parameters and capacities alongside a canonical lower-bound construction and a matching upper-bound argument.

3.4 The Canonical Set: the Lower Bound

  • The section’s roadmap states that an explicit MVS S* of size cap(G) gives the lower bound, followed by a matching upper bound and exact formula.The supplied construction fragment fixes witnesses and runs for latent twin-, unit-, and twin-cycles, but does not show the full definition of S*.Source: §3 · p. 3, §3.4 · p. 9

3.1 Preliminaries

  • A maximum MVS can be chosen to avoid articulation points [21], enabling analysis through cycle and tree components.The decomposition cuts at articulation points on cycles; its components are cycle components and tree components attached at shared boundary vertices.Source: §3.1 · pp. 4–5

3.2 Basic Geometry of a Cycle Component

  • Every cycle component is isometric, and for an MVS avoiding articulation points, selected vertices in a tree component can only be leaves of G.For a run of k consecutive vertices outside A on a cycle, its arc is uniquely shortest between its endpoints when k < τC; when k ≥ τC, the complementary arc is shortest.Source: §3.2 · p. 6

3.3 Cycle Types and Capacity

  • Cycle components are classified as twin, unit, latent twin, or zero cycles, with respective capacities 2, 1, 1, and 0; capacity is each component’s net contribution to a maximum MVS.A latent twin-cycle contributes two vertices of the cycle but forfeits the leaf of one adjacent beard, so its net contribution is 2 − 1 = 1.Source: §3.3 · p. 7
  • A branch at a cycle boundary has capacity at least 1, and has capacity 1 exactly when it is a beard.The classification uses beard boundary vertices as witnesses for latent twin-cycles; deactivating a non-beard branch costs at least two, while a beard branch costs one.Source: §3.3 · pp. 8–9

3.4 The Canonical Set: the Lower Bound

  • The canonical set S* avoids articulation vertices, has size cap(G), and is a mutual visibility set, so µ(G) ≥ cap(G) = 2n2 + nlt + n1 + ℓ(G).Its visibility follows from local traversability on cycle components and the articulation-free interiors of paths through tree components.Source: §3.4 · pp. 9–11

3.5 The Upper Bound and the Exact Formula

  • For any MVS avoiding articulation points, each cycle's selected vertices satisfy a local exchange inequality, while laminar inactive branches prevent double-counting when the bounds are summed.The inactive branches are laminar, and their maximal members are pairwise disjoint.Source: §3.5 · pp. 11–12
  • For every cactus graph G that is not a simple cycle, the theorem gives equal values for µ(G) and cap(G), each exactly 2n2 + nlt + n1 + ℓ(G).Proposition 22 states that S∗ is an MVS of G and consequently µ(G) ≥ cap(G) = 2n2 + nlt + n1 + ℓ(G).Source: §3.4 · p. 10, §3.5 · p. 13
  • For every cactus graph G that is not a simple cycle, µ(G) ≤ 2|C(G)| + ℓ(G), with equality exactly when every cycle component is a twin-cycle.Source: §3.5 · p. 13
  • A maximum MVS and µ(G) can be computed sequentially in O(n) time for a cactus graph on n vertices.Source: §3.5 · p. 14
  • A maximum MVS need not select cap(C) vertices from every cycle: in the stated 5-cycle example, a maximum set takes two cycle vertices while omitting a pendant leaf.Here λC = τC = 2 and µ(G) = 3; the two maximum sets are {a, b, w1} and {a, w1, r}.Source: §3.5 · p. 14

4 Self-Stabilizing Algorithms for a Maximum Mutual Visibility Set

Both self-stabilizing algorithms construct the maximum MVS S∗, using different BFS strategies to trade space for stabilization time. The section specifies the system model and develops Algorithm 1 from a four-phase strategy into explicit rules.

4 Self-Stabilizing Algorithms for a Maximum Mutual Visibility Set

  • Both algorithms compute S∗; Algorithm 1 uses a single BFS tree for space efficiency, while Algorithm 2 uses parallel BFS trees to optimize stabilization time.Algorithm 2 replaces the global tree with local BFS trees from high-degree vertices, allowing decisions before a global BFS tree stabilizes.Source: §4 · p. 14

4.1 System Model and Specification

  • The model uses a cactus graph, shared-memory state reading, distinct polynomial-domain identifiers, a common process-count bound, and a predetermined leader.The leader has degree at least three; distance variables use the finite domain {0, 1, . . . , N}.Source: §4.1 · p. 15
  • Under the distributed daemon, arbitrary nonempty subsets of enabled processes execute simultaneously, and weak fairness ensures continuously enabled processes eventually execute.Round complexity is meaningful under this fairness assumption; the initial configuration may be arbitrary.Source: §4.1 · p. 15
  • A legitimate configuration is a fixed point whose output is the maximum MVS containing no articulation point, a restriction shown to be without loss of generality.Both algorithms are silent: after reaching legitimacy, their outputs remain constant.Source: §4.1 · p. 15

4.2 Algorithm 1: A Space-Efficient Self-Stabilizing Algorithm

  • Algorithm 1 builds a BFS tree, identifies cycles and articulation points, detects cycle runs and eligible beards, then selects cycle vertices and leaves for S∗.Cycle identification uses non-tree edges and a leaf-to-root wave; a beard is deactivated only for a latent twin-cycle witness.Source: §4.2 · p. 16

4.3 The Rules of Algorithm 1

  • The complete rules replace informal propagation descriptions with explicit local assignments that overwrite arbitrary initial values and use finite variable domains.This purge behavior removes corrupted states and contributes to silence.Source: §4.3 · pp. 16–17

A layered evaluation lemma

The layered evaluation lemma bounds stabilization from the dependency structure of variables. It gives both per-variable convergence times and a global bound from the depths of the layers.

A layered evaluation lemma

  • A variable at dependency depth ∆(y) holds its prescribed value from the end of round ∆(y) + 1, from every initial configuration under a weakly fair daemon.Dependency depth is zero when the rule refers to no other variable and otherwise one plus the maximum depth of referenced variables.Source: A layered evaluation lemma · p. 17
  • When each layer has an acyclic evaluation order and depends only on its in-neighbours, all variables stabilize within 1 + Σ(hi + 1) rounds.Here hi is the depth of layer i.Source: A layered evaluation lemma · p. 17
  • A selected set of variables with maximum dependency depth O(k) stabilizes in O(k) rounds, regardless of the depths of other variables.The per-variable form is useful when analyzing local stabilization before the whole system stabilizes.Source: A layered evaluation lemma · pp. 17–18
  • The lemma makes each aggregation’s evaluation order, depth, and purge behavior explicit, replacing informal claims that information propagates within a component.Its proof proceeds by induction on dependency depth.Source: A layered evaluation lemma · pp. 17–18

Notation and variables

The notation organizes process state around graph structure and cycle incidences. Records track cycle-specific computations, while the cactus structure bounds average storage.

Notation and variables

  • A non-tree edge is recognized locally at both endpoints and identified by the ordered pair of endpoint IDs, which names its cycle.Processes store a constant part plus one record per incident cycle.Source: Notation and variables · p. 18
  • Per-cycle records hold BFS and source data, cycle size and type, run lengths, beard and witness flags, and selection information.The representation lets a vertex on multiple cycles maintain separate cycle identifiers and values.Source: Notation and variables · p. 18
  • Each record uses O(log n) bits, giving O(n log n) total storage and O(log n) bits per process on average in a cactus.A process incident to γv cycles may use Θ(γv log n) bits, with γv as large as Θ(n).Source: Notation and variables · p. 18

Layers 1–2: BFS tree and cycle identification

The first two layers construct a rooted BFS tree and identify each cactus cycle from its non-tree edge. Their stabilization bounds are independent of arbitrary initial states.

Layers 1–2: BFS tree and cycle identification

  • Because cactus cycles are edge-disjoint, each cycle has one non-tree edge, whose endpoint-ID pair supplies a cycle identifier without prior cycle-vertex knowledge.The endpoints locally check whether their edge is a non-tree edge.Source: Layers 1–2: BFS tree and cycle… · pp. 18–19
  • Pinned BFS distances are correct through radius k after k + 1 rounds, and all distances are correct after D + 1 rounds.Parent pointers become correct one round after the corresponding distances.Source: Layers 1–2: BFS tree and cycle… · pp. 19–20
  • After Layers 1–2 stabilize, exactly the vertices of each cycle hold its identifier, and its unique minimum-depth vertex receives both endpoint distances.No vertex outside that cycle holds the identifier.Source: Layers 1–2: BFS tree and cycle… · p. 20
  • A fabricated cycle identifier disappears in one round because a process retains it only when supported by an anchor or forwarding child.The propagation wave stops at the cycle’s lowest common ancestor.Source: Layers 1–2: BFS tree and cycle… · p. 20

Layers 3–4: cycle geometry and articulation points

The layers establish an ordered representation of each cycle and identify its distinguished vertex as an articulation point. This provides a path structure on which later run computations can operate.

Layers 3–4: cycle geometry and articulation points

Layers 5–8: runs and λC

Layers 5–8 compute run lengths along cycle paths, then propagate each cycle’s maximum run length, λC.

Layers 5–8: runs and λC

Layers 9–13: beards, witnesses and deactivation

The rules identify beard boundaries and use positions, rather than identifiers, to choose a witness consistently.

Layers 9–13: beards, witnesses and deactivation

Layers 14–15: classification and output

Algorithm 1 classifies cycles and constructs the canonical maximum MVS, with a unique legitimate configuration reached in O(D) rounds. Algorithm 2 instead computes component-local information using parallel BFS trees so cycle work need not wait for a global BFS tree.

4.4 Correctness and Complexity of Algorithm 1

  • The rules admit one legitimate configuration whose output is the maximum MVS S∗, containing no articulation point.Source: §4.4 · pp. 22, 25
  • Cycle geometry is computed from BFS depths, which determine the cycle size and order its vertices so neighboring positions correspond to cycle neighbors.Source: §4.4 · p. 23
  • Beard detection checks branch structure, then one witness per cycle is deactivated and run maxima are recomputed with that witness excluded.Source: §4.4 · p. 24

Layers 14–15: classification and output

  • Twin and latent twin-cycles select the endpoints of the unique longest deactivated run, while unit-cycles select one vertex from a longest run and zero-cycles select none.Source: §4.4 · p. 24

4.4 Correctness and Complexity of Algorithm 1

  • Under the weakly fair distributed daemon, Algorithm 1 reaches its legitimate configuration in O(D) rounds and is silent.Source: §4.4 · p. 25
  • Algorithm 1 uses O(log n) bits per process on average, but a process on γv cycles can require Θ(γv log n) bits, with γv as large as Θ(n).Source: §4.4 · pp. 25–26
  • No non-trivial space lower bound is known for maximum MVS itself; the cited Ω(log n) bound applies to the BFS-tree strategy, not the problem.Source: §4.4 · p. 25

4.5 Algorithm 2: A Component-Local Self-Stabilizing Algorithm

  • Algorithm 2 uses parallel BFS trees rooted at degree-at-least-three vertices, allowing cycle computations to finish in O(|C|) rounds without waiting for other components.Source: §4.5 · p. 26

Instances, local roots and the rules of Algorithm 2

Algorithm 2 replicates Algorithm 1 across roots of degree at least three, then selects a local root for each cycle and evaluates that cycle’s final rules in its selected instance.

Instances, local roots and the rules of Algorithm 2

  • Algorithm 2 runs an Algorithm 1 instance for every vertex of degree at least three, with that vertex replacing the leader.Theorem 37 applies to each instance.Source: Instances, local roots and the rules… · p. 26
  • Each cycle chooses its smallest-identifier degree-at-least-three vertex as root, and all its vertices select the same root using broadcast distances.A cycle contains such a boundary vertex because the graph is connected and is not a simple cycle.Source: Instances, local roots and the rules… · p. 26
  • Cycle records can be matched across instances by each vertex’s unordered pair of cycle neighbours, which is independent of the instance.The cycle identifier itself can vary with the root.Source: Instances, local roots and the rules… · pp. 26–27
  • Only the selected instance evaluates the final layers for a cycle and its attached trees, keeping witness tie-breaking consistent for latent twin-cycles.Combining deactivation flags across instances could forfeit two leaves instead of one.Source: Instances, local roots and the rules… · p. 27

Complexity analysis of Algorithm 2

Algorithm 2 stabilizes in time determined by the largest cycle and tree components, with a matching lower bound on a family of graphs. Its memory cost can be higher than Algorithm 1’s, though the time advantage can matter when those components are small relative to the diameter.

Complexity analysis of Algorithm 2

  • O(|Cmax| + |Tmax|) rounds suffice under the distributed daemon, and Proposition 44 shows an Ω(|Cmax| + |Tmax|) lower bound on a graph family.The lower bound is asymptotically tight even when the diameter is arbitrarily larger than these parameters.Source: Complexity analysis of Algorithm 2 · pp. 27–28
  • O(|Cmax| + |Tmax|) rounds suffice because each cycle and its attached trees stabilize using dependencies of depth O(|Cmax| + |Tmax|).The proof keeps the relevant evaluation within a radius-|Cmax| + |Tmax| ball around the selected root, regardless of the graph’s diameter.Source: Complexity analysis of Algorithm 2 · p. 27
  • Algorithm 2’s lower bound is not implied by diameter: the paper gives graphs where |Cmax| + |Tmax| = Θ(s + t) while D = Θ(m + s + t).The lower bound is for a family of instances, not every cactus graph.Source: Complexity analysis of Algorithm 2 · p. 28
  • When |Cmax| + |Tmax| = O(1), Algorithm 2 can stabilize in O(1) rounds even when D = Θ(n), whereas Algorithm 1 needs Θ(D) rounds.The remark also cautions that Ω(|Cmax| + |Tmax|) is not a lower bound on every cactus graph.Source: Complexity analysis of Algorithm 2 · p. 28

4.6 Comparison of the Two Algorithms

  • Algorithm 2’s memory is dominated by O(|Vδ3+| log D), which can exceed Algorithm 1’s O(γv log n) per-process cost when high-degree vertices are numerous.When |Cmax| + |Tmax| = o(D) and |Vδ3+| is small, Algorithm 2 can offer faster stabilization with manageable memory.Source: §4.6 · p. 29

5 Conclusion and Open Problems

The paper determines the cactus-graph mutual visibility number and gives two self-stabilizing constructions of maximum sets. It leaves extensions to broader graph classes and non-trivial space lower bounds open.

5 Conclusion and Open Problems

  • The cactus-graph mutual visibility number is µ(G) = 2n2 + nlt + n1 + ℓ(G), and the two algorithms construct a maximum MVS.Algorithm 1 stabilizes in O(D) rounds with O(log n) average space per process; Algorithm 2 stabilizes in O(|Cmax| + |Tmax|) rounds, asymptotically tightly even when those parameters are o(D), at increased memory cost.Source: §5 · p. 29
  • Open problems include determining the MVN for outerplanar, series-parallel, and bounded-treewidth graphs, and establishing non-trivial space lower bounds.Whether Algorithm 1’s worst-case per-process space can be reduced to O(log n) also remains open.Source: §5 · p. 29
Loading 2609.07253v1…