arXiv CSopen access

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

The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions Yonghwan Kim # Nagoya Institute of Technology, Aichi, Japan

Yuichi Sudo # Hosei University, Tokyo, Japan

arXiv:2609.07253v1 [cs.DC] 7 Sep 2026

Abstract Given a graph G = (V, E), let S (⊆ V ) be a set of vertices. Two vertices are 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 Mutual Visibility Set (MVS) if every pair of vertices in S is mutually visible. The concept of MVSs 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 NP-complete. Thus, prior work has focused on finding maximal MVSs 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(|Cmax | + |Tmax |) rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where |Cmax | + |Tmax | = o(D). 2012 ACM Subject Classification Mathematics of computing → Graph theory; Computing methodologies → Distributed algorithms Keywords and phrases mutual visibility, cactus graph, self-stabilization Acknowledgements This work was supported by JSPS KAKENHI Grant Numbers JP23K24825, JP25K03078, JP25K03079, JP26K02865, JP26K23809, and JST FOREST Program JPMJFR226U.

1

Introduction

Distributed systems must cope with the absence of a global clock, only partial knowledge of the global state, and transient faults that silently drive the system into an illegitimate configuration. A self-stabilizing algorithm [10] tolerates such faults by guaranteeing convergence to a legitimate configuration within finite time from any initial configuration, without external intervention. A natural structural question in distributed network settings is which subsets of processors can communicate efficiently without mutual interference. This is captured by the notion of a Mutual Visibility Set (MVS), introduced by Di Stefano [21]. Given a graph G = (V, E), a set S ⊆ V is an MVS if every pair of vertices in S is connected by a shortest path whose internal vertices all lie outside S. In a distributed system modeled by G, a maximum MVS is the largest set of processes that can be connected pairwise by shortest paths none of which is routed through another member of the set. This is the natural formalisation of a network of mutually distrusting parties—each party is willing to relay traffic for others, but is not willing to have its own traffic relayed by a peer, so that any two members must be joined by a shortest path whose intermediate vertices are all non-members. The same condition arises when the members of the set are the end-points of concurrent shortest-path communications and a member must not be forced to act as a relay while it is itself communicating. Mutual visibility originates in the study of mobile robots with obstructed visibility, where a robot © Yonghwan Kim; licensed under Creative Commons License CC-BY 4.0 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

A Maximum Mutual Visibility Set on a Cactus Graph

blocks the line of sight of two robots collinear with it [20], and the graph version studied here replaces lines of sight by shortest paths [21]. The mutual visibility number (MVN), denoted µ(G), is the size of the largest MVS on the given graph. Determining a maximum MVS or finding MVN is computationally intractable on general graphs [21] and hard to approximate for large diameter [2]. Motivated by these hardness barriers, prior work has restricted attention to specific graph classes, obtaining exact formulas for paths, cycles, block graphs, cographs, grids, and distance-hereditary graphs [21, 4], as well as various graph products [6, 18]. Despite this sustained activity, the MVN of cactus graphs—a fundamental class of low-treewidth graphs that generalizes both trees and cycles—has not been determined. In this paper we resolve the case of cactus graphs. We establish the exact MVN of any cactus graph via a closed-form formula, and propose two self-stabilizing algorithms that construct a maximum MVS. Our contributions are as follows. 1. We introduce a cycle–tree decomposition of a cactus graph G and classify each cycle component as a zero-cycle, unit-cycle, twin-cycle, or latent twin-cycle, leading to the exact formula µ(G) = 2n2 + nlt + n1 + ℓ(G), where n1 , n2 , nlt , and ℓ(G) denote the numbers of unit-cycles, twin-cycles, latent twin-cycles, and leaves of G, respectively. No exact characterization of the MVN for cactus graphs was previously known. 2. We propose Algorithm 1, a self-stabilizing algorithm that constructs a maximum MVS using a single-root BFS tree. It stabilizes in O(D) rounds and uses O(log n) bits per process on average, where D is the diameter of G and n = |V |. 3. We propose Algorithm 2, a self-stabilizing algorithm that runs parallel BFS trees from all high-degree vertices, enabling component-wise early termination. It stabilizes in O(|Cmax | + |Tmax |) rounds, where |Cmax | and |Tmax | are the sizes of the largest cycle component and of the largest tree component of G. This bound is component-local: we exhibit a family of cactus graphs on which |Cmax | + |Tmax | is an arbitrarily small fraction of D and on which every correct self-stabilizing algorithm nevertheless requires Ω(|Cmax | + |Tmax |) rounds, so the bound is asymptotically tight as a function of these two parameters. Both algorithms operate under the distributed daemon—the weakest standard scheduling assumption—and are guaranteed to converge to a maximum MVS from any initial configuration. The rest of the paper is organized as follows. Section 2 reviews related work. Section 3 derives the MVN formula for cactus graphs and gives all of its proofs. Section 4 fixes the computational model, describes the two self-stabilizing algorithms, gives the complete set of rules of Algorithm 1 together with their correctness and complexity analysis, and proves the lower bound that makes the stabilization time of Algorithm 2 asymptotically tight. Section 5 concludes with open problems. This is the full version of the paper: every proof is given in place, and the parts that a page-limited presentation can only summarise — the rules of Algorithm 1, the layered analysis on which the round complexity rests, and the construction of the lower-bound family — are developed here in detail.

2

Related Work

Self-stabilization was introduced by Dijkstra in 1974 [10] as a paradigm for designing faulttolerant distributed systems, and self-stabilizing solutions are now known for most classical distributed problems; see Dolev [11] and Altisen et al. [1] for textbook treatments, and [16] for a survey of graph-theoretic problems. Two results from this line are directly relevant

Y. Kim and Y. Sudo

here. First, for silent algorithms—those whose communication registers stop changing after stabilization—Dolev, Gouda and Schneider [12] proved an Ω(log n) lower bound on the memory per register for problems such as leader election and spanning tree construction; Remark 40 discusses why it does not transfer to the maximum MVS problem. Second, stronger fault models such as snap-stabilization [9], superstabilization [13] and Byzantine-tolerant stabilization [15] have been developed; we work in the classical model under the distributed daemon. Visibility problems in distributed computing originate in mobile robot systems: Di Luna et al. [20] solved the mutual visibility problem for anonymous robots with obstructed visibility in the plane. The graph-theoretic formulation of the MVS problem was introduced by Di Stefano [21], who proved that deciding whether a graph admits an MVS of size at least k is NP-complete and determined the MVN of several graph classes, including block graphs, trees, Cartesian products of paths and cycles, complete bipartite graphs, and cographs. Bilò et al. [2] proved strong inapproximability results: the problem is not approximable within n1/3−ε for graphs of diameter at least three and is APX-hard for diameter two. Because the general problem is intractable, subsequent work has either restricted the graph class or introduced variants of mutual visibility. Exact formulas for the MVN are known for paths, cycles, block graphs, cographs and grids, and the MVN is computable in linear time on distance-hereditary graphs [4]; further results cover Cartesian products and triangle-free graphs [6], strong products [7], graphs of diameter two [8], hypercubes [18], and Sierpiński-type graphs [19]. The total, dual and outer variants were proposed in [5], and an independent variant in [3]. The MVN of cactus graphs has not been determined; the present paper settles it and, in addition, gives two self-stabilizing algorithms that construct a maximum MVS.

3

The Mutual Visibility Number on Cactus Graphs

This section is organised as follows. Section 3.1 fixes the terminology and recalls the two known results on which our analysis rests. Section 3.2 collects the elementary metric facts about a single cycle component, and in particular introduces the two parameters λC and τC . Section 3.3 uses them to classify cycle components and to define the capacity cap(·), which is the quantity that the main theorem computes. Section 3.4 exhibits an explicit MVS S ∗ of size cap(G) (the lower bound), and Section 3.5 proves the matching upper bound and the exact formula. All proofs are given in full and in place; nothing is deferred.

3.1

Preliminaries

All graphs considered in this paper are finite, simple, and undirected. Let G = (V, E) be a connected graph with vertex set V = {v1 , v2 , . . . , vn } and edge set E. For a vertex vi ∈ V , we denote by N (vi ) the open neighborhood of vi , i.e., N (vi ) = {vj ∈ V | {vj , vi } ∈ E}. We denote by δ(vi ) the degree of vertex vi , i.e., the number of its adjacent vertices. A vertex of degree one is a leaf of G, and we write ℓ(G) for the number of leaves of G; more generally, for a subgraph H of G we write ℓG (H) for the number of leaves of G that lie in H, so that ℓ(G) = ℓG (G). We write dG (u, v) for the distance between u and v in G, i.e., the length of a shortest u-v path in G. The indices of v1 , . . . , vn are used only to break ties in an otherwise arbitrary but fixed way; no property of the enumeration is assumed.

XX:3

XX:4

A Maximum Mutual Visibility Set on a Cactus Graph

𝝀𝟏 = 𝟐 𝝉𝟏 = 𝟏

𝑪𝟑 𝝀𝟑 = 𝟐, 𝝉𝟑 = 𝟐

𝑪𝟏

𝑪𝟐 𝝀𝟐 = 𝟏 𝝉𝟐 = 𝟏

𝑪𝟒

𝝀𝟒 = 𝟏 𝝉𝟒 = 𝟐

𝑪𝟓

𝑪𝟖

𝝀𝟓 = 𝟒, 𝝉𝟓 = 𝟑

𝝀𝟖 = 𝟏 𝝉𝟖 = 𝟐

𝝀𝟔 = 𝟐, 𝝉𝟔 = 𝟐

𝑪𝟔

𝑪𝟕

𝝀𝟕 = 𝟏 𝝉𝟕 = 𝟏

𝑪𝟗 𝝀𝟗 = 𝟑, 𝝉𝟗 = 𝟏

Figure 1 An example of a cactus graph and its cycle components with parameters.

▶ Definition 1 (Cactus Graph). A connected graph G = (V, E) is a cactus graph if every edge of G belongs to at most one simple cycle. Equivalently, G is a cactus graph if and only if every biconnected component of G is either a single edge or a simple cycle. Figure 1 illustrates an example of a cactus graph. Note that simple cycles are special cases of cactus graphs, and the MVN of cycles can be easily obtained [21]. Therefore, we focus on cactus graphs that are not simple cycles. We denote by C(G) the set of all simple cycles in G, and write |C(G)| for the number of cycles in G. Moreover, we write vi ∈ ej (where vi ∈ V and ej ∈ E) if vi is an endpoint of ej . ▶ Definition 2 (Articulation Point). Let G = (V, E) be a connected graph. A vertex v ∈ V is an articulation point of G if the subgraph G − v = (V \ {v}, E \ {e ∈ E | v ∈ e}) is disconnected. We denote by A(G) the set of all articulation points of G. We now define a canonical decomposition of a cactus graph into cycle components and tree components by cutting at articulation points that lie on cycles. ▶ Definition 3 (Cycle–Tree Decomposition). Let G be a cactus graph, and let AC (G) = {v ∈ A(G) | v belongs to at least one cycle in C(G)} be the set of articulation points of G that lie on at least one cycle. The cycle–tree decomposition of G consists of the following two types of components. 1. For each simple cycle Ci ∈ C(G), the cycle component induced by Ci is the subgraph G[V (Ci )]. Every vertex in V (Ci ) ∩ AC (G) is called a boundary vertex of cycle component Ci . S 2. Let G′ = G − Ecyc , where Ecyc = C∈C(G) E(C) denotes the set of all edges belonging to at least one cycle. Each connected component of G′ with at least two vertices is called a tree component of G. Every vertex of a tree component Ti that belongs to AC (G) is called a boundary vertex of Ti . The boundary vertices serve as attachment points shared between a cycle component and one or more adjacent components, and are included in both the relevant cycle component and the adjacent component(s). In Figure 1, the vertices in AC (G)—that is, articulation points that belong to at least one cycle—are depicted as grid-patterned vertices. Note that these vertices are the boundary vertices of some components. The cactus graph in Figure 1 has 9 cycle components. Since every edge of a tree component is a bridge of G, every vertex that is internal to a tree component (i.e., has degree at least two in that component) is an articulation point of G; we use this fact repeatedly.

Y. Kim and Y. Sudo

XX:5

▶ Definition 4 (Beard and Non-Beard Tree Component). Let G be a cactus graph, and let T be a tree component of G in its cycle–tree decomposition (Definition 3). We say that T is a beard of G if the following three conditions are all satisfied: (B1) T is a path graph, i.e., T ∼ = Pk for some k ≥ 2; (B2) exactly one endpoint of T is a boundary vertex of T , and that boundary vertex is shared with exactly one cycle component of G; and (B3) the other endpoint of T is a leaf of G (i.e., has degree one in G), and every internal vertex of T (i.e., every vertex of degree two in T ) is not a boundary vertex of any component in the cycle–tree decomposition of G. A tree component that does not satisfy all three conditions is called a non-beard tree component of G. ▶ Remark 5. A beard is a pendant path hanging off exactly one cycle, with its free end a leaf of G and no internal vertex shared with another component; the smallest beard is P2 . A non-beard tree component either branches (violating (B1)), has two boundary vertices (violating (B2)), or has an internal vertex that is an attachment point of another component (violating (B3)). Finally, we recall the two results of Di Stefano [21] that our analysis builds upon. ▶ Lemma 6 ([21]). For every simple cycle C with |C| ≥ 3 we have µ(C) = 3; that is, no four vertices of C are pairwise mutually visible, and some three of them always are. ▶ Lemma 7 ([21]). Every graph G admits a maximum MVS that contains no articulation point of G. By Lemma 7 we may, and from now on always do, restrict attention to MVSs that avoid A(G).

3.2

Basic Geometry of a Cycle Component

Throughout the remainder of Section 3, G denotes a cactus graph that is not a simple cycle. We first fix the two pieces of notation that the whole analysis is phrased in — the branch at a boundary vertex and the parameters λX C , τC — and then record the metric facts they obey. ▶ Definition 8 (Branch). Let C be a cycle component of G and v ∈ V (C) ∩ AC (G). The branch of C at v, denoted Gv , is the union of all connected components of G − v that do not contain C \ {v}. A union of components is taken so that the definition remains meaningful when v has several branches, e.g., when v lies on two cycles or carries two pendant paths. Writing Hv for the component of G − v containing C \ {v}, we obtain the partition V = V (Gv ) ⊔ {v} ⊔ V (Hv ).

(1)

The branches of one fixed cycle component at its distinct boundary vertices are pairwise disjoint, being unions of distinct components of G minus those vertices; and a branch determines the pair (C, v) it comes from (Lemma 25(i)). The family of all branches is, however, not laminar: if v lies on two cycles C, C ′ and also carries a pendant path T , then the branch of C at v and the branch of C ′ at v both contain T and neither contains the other. Laminarity does hold for the sub-family of branches that contain no vertex of a given MVS (Lemma 25(i)), which is all we shall need.

XX:6

A Maximum Mutual Visibility Set on a Cactus Graph

▶ Definition 9 (Parameters λX C and τC ). Let C be a cycle component of G and let AC = V (C) ∩ AC (G) be its set of boundary vertices. For X ⊆ AC we let
λX C denote the maximum number of consecutive vertices of C that belong to V (C) \ AC ∪ X; that is, the length of the longest run of consecutive non-articulation-point vertices of C once the vertices of X have been deactivated (i.e., are treated as non-articulation points). Such a maximal {v} run is called an X-free run of C. We abbreviate λC = λ∅C and λvC = λC . Finally we set  τC = (|C| − 1)/2 , so that 2τC + 1 ≤ |C| ≤ 2τC + 2. Figure 1 shows the parameters λC and τC for each cycle component. ▶ Observation 10. Every cycle component C of G is an isometric subgraph of G: for all u, v ∈ V (C) we have dG (u, v) = dC (u, v), and every shortest u–v path of G is one of the two u–v arcs of C. Proof. Since G is a cactus, C is a biconnected component (block) of G; two distinct blocks share at most one vertex, so any path leaving C at a vertex x must re-enter C at the same vertex x. Hence no path between two vertices of C is shorter than the shorter of the two arcs of C. ◀ ▶ Observation 11. Let S be an MVS of G with S ∩ A(G) = ∅ and let T be a tree component of G. Then S ∩ V (T ) consists of leaves of G only. Moreover, the internal vertices of any path inside T are articulation points of G, hence they never belong to S. Proof. Let u ∈ V (T ) not be a leaf of G. If u has degree at least two in T , then, since every edge of T is a bridge of G, deleting u disconnects G and u ∈ A(G). Otherwise u has degree one in T but degree at least two in G, so u is incident with an edge of a cycle; hence u ∈ V (T ) ∩ AC (G) is a boundary vertex of T and again u ∈ A(G). In both cases u ∈ / S. An internal vertex of a path inside T has degree at least two in T and is covered by the first case. ◀ ̸ ∅, ▶ Lemma 12 (Arc geometry). Let C be a cycle component of G, let A ⊆ V (C) with A = and let P be a maximal run of consecutive vertices of V (C) \ A, say |P | = k. Let p, q ∈ A be the two vertices of A adjacent to the two ends of P (possibly p = q, which happens exactly when |A| = 1). Then the p–q arc through P has length k + 1, the complementary arc has length |C| − k − 1, and (i) if k < τC , the arc through P is the unique shortest p–q path of G; (ii) if k ≥ τC , the complementary arc is a shortest p–q path of G. Moreover, for every u ∈ P at distance j from p along P (so 1 ≤ j ≤ k), if j ≤ τC then the sub-path of P from p to u is the unique shortest p–u path of G. Proof. By Observation 10 the only p–q paths that can be shortest are the two arcs, whose lengths are k + 1 and |C| − k − 1. The arc through P is the unique shortest one if and only if k + 1 < |C| − k − 1, i.e., 2k + 2 < |C|, and the complementary arc is a shortest one if and only if |C| ≤ 2k + 2. Since 2τC + 1 ≤ |C| ≤ 2τC + 2, we have 2k + 2 < |C| ⇐⇒ k < τC and |C| ≤ 2k + 2 ⇐⇒ k ≥ τC , which gives (i) and (ii). For the last claim, the two p–u arcs have lengths j and |C| − j, and j ≤ τC gives 2j ≤ 2τC < |C|. ◀ Lemma 12 explains the threshold τC : a run is blocking when it is strictly shorter than τC , neutral when it equals τC , and free when it exceeds τC .

𝒂

𝒃 𝒄

𝒇

𝒃

𝒄 𝒅

𝒈 𝒇

𝒆

𝒃𝒂

𝒂

𝒇

𝒈 𝒇𝒆

𝒄

𝒂

𝒄

𝒃

𝒅

XX:7

𝝀=𝟐, 𝝉=𝟐

𝝀=𝟏, 𝝉=𝟐

𝒂

𝒃

𝒆

𝒅

𝒆

Y. Kim and Y. Sudo

𝒂

𝒇

𝒅

𝒅

𝒆

𝒃

𝒄

𝒈 𝒆

𝒅

𝒂

𝒄

𝒇

𝒃 𝒄

𝒇 𝒆

𝒅

𝝀=𝟒, 𝝉=𝟑

𝝀= 𝟒 ,𝟐𝝉, 𝝉==𝟑𝟐 𝝀=

𝝀 = 𝟏, 𝝀𝒄 = 𝟑,𝝉 = 𝟐

𝝀=𝟏, 𝝉=𝟐

(a) twin-cycle

(b) unit-cycle

(c) latent twin-cycle

(d) zero-cycle

Figure 2 The four types of cycle component. Grey vertices are boundary vertices.

3.3

Cycle Types and Capacity

▶ Definition 13 (Cycle Component Types). Let C be a cycle component of G. A boundary vertex v ∈ AC is a beard boundary vertex of C if the branch Gv (Definition 8) is a beard of G (Definition 4). We classify C as follows. C is a twin-cycle if λC > τC (refer to Figure 2(a)); C is a unit-cycle if λC = τC (refer to Figure 2(b)); ∗ C is a latent twin-cycle if λC < τC and λvC > τC for some beard boundary vertex v ∗ of C, which we call a witness for C (refer to Figure 2(c)); C is a zero-cycle otherwise (refer to Figure 2(d)). The four types are mutually exclusive and exhaustive. We denote by n0 , n1 , n2 , nlt the numbers of zero-, unit-, twin- and latent twin-cycles of G, so that n0 + n1 + n2 + nlt = |C(G)|. ▶ Definition 14 (Capacity). The capacity of a cycle component C is    2 if C is a twin-cycle, cap(C) = 1 if C is a unit-cycle or a latent twin-cycle,   0 if C is a zero-cycle, ▶ Definition 15 (Branch capacity). Let C be a cycle component of G and v ∈ AC . We say that a cycle component C ′ of G lies below (C, v) if V (C ′ ) ⊆ V (Gv ) ∪ {v}, and we write C(C, v) for the set of such cycle components. The branch capacity of C at v is X cap∗ (C, v) = ℓG (Gv ) + cap(C ′ ). C ′ ∈C(C,v)

Finally, the capacity of G is cap(G) = ℓ(G) +

P

C∈C(G) cap(C).

Note that C ∈ / C(C, v), while every cycle component through v other than C does lie below (C, v); counting v itself is essential. For instance, if G consists of two 4-cycles C, C ′ sharing a single vertex v, then Gv = C ′ \ {v} contains no leaf of G and no cycle component as a subgraph, yet cap∗ (C, v) = cap(C ′ ) = 2, which is the correct value. The capacity of C is what C contributes net to a maximum MVS: a latent twin-cycle contributes two vertices of C but forfeits the leaf of one adjacent beard, hence 2 − 1 = 1. Summing over all components gives X cap(G) = ℓ(G) + cap(C) = 2n2 + nlt + n1 + ℓ(G), (2) C∈C(G)

and Theorem 26 will state that µ(G) = cap(G). The following two lemmas make the classification well behaved.

XX:8

A Maximum Mutual Visibility Set on a Cactus Graph

▶ Lemma 16. Let C be a cycle component and X ⊆ AC with λX C > τC . Then the X-free run of length λX is unique. Moreover, if C is a latent twin-cycle with witness v ∗ and C ∗ ∗ X = {v }, then v is an internal vertex of that run; in particular both endpoints of the run are non-articulation points of G. Proof. Two distinct X-free runs of length λ > τC are separated by at least one vertex on each side, hence |C| ≥ 2λ + 2 ≥ 2τC + 4 > 2τC + 2 ≥ |C|, a contradiction. For the second claim, let α and β be the lengths of the two ∅-free runs of C adjacent to v ∗ (with α = 0, resp. β = 0, if v ∗ is adjacent to another boundary vertex on that ∗ side). Deactivating v ∗ merges exactly these two runs, so λvC = max{λC , α + 1 + β}; since ∗ ∗ λC < τC < λvC we must have α + 1 + β = λvC > τC . The vertex v ∗ is an endpoint of the merged run if and only if α = 0 or β = 0. If α = 0, then β > τC − 1, i.e., β ≥ τC , whereas β ≤ λC < τC — a contradiction; the case β = 0 is symmetric. Hence α, β ≥ 1 and v ∗ is internal. Every vertex of the run other than v ∗ lies outside AC and is therefore not an articulation point of G, so in particular the two endpoints are not. ◀ ▶ Lemma 17 (Value of a branch). Let C be a cycle component of G and v ∈ AC . Then cap∗ (C, v) ≥ 1, and cap∗ (C, v) = 1 holds if and only if Gv is a beard of G. Proof. We argue by induction on |V (Gv )|, the induction hypothesis being that the statement holds for every branch with strictly fewer vertices. Note first that Gv ̸= ∅, since v is an articulation point and Hv is only one of the components of G − v. Case 1: C(C, v) = ∅. Then v lies on no cycle other than C, and Gv contains no cycle of G; hence Gv contains no edge of Ecyc and T := G[V (Gv ) ∪ {v}] is exactly the tree component of G containing v. Every component of Gv is a tree, and a vertex of it at maximum distance from v has degree one in G; hence cap∗ (C, v) = ℓG (Gv ) ≥ 1. Equality holds if and only if T contains exactly one leaf of G, i.e. if and only if T is a path with v as one endpoint and a leaf of G as the other. In that case (B1) holds, (B2) holds because v lies on the single cycle C, and (B3) holds because an internal vertex of T lying in AC (G) would lie on a cycle contained in Gv , contradicting C(C, v) = ∅. Hence cap∗ (C, v) = 1 if and only if Gv is a beard. Case 2: C(C, v) ̸= ∅. Choose C ′ ∈ C(C, v) at minimum distance from v and let x be the vertex of C ′ closest to v; thus x = v when v ∈ V (C ′ ). In either case x is an articulation point of G lying on C ′ (if x = ̸ v it separates C ′ from v; if x = v it separates C ′ from C), so ′ x ∈ AC ′ . Put k = |AC ′ |. k ′ = 1: then AC ′ = {x}, so λC ′ = |C ′ | − 1 > τC ′ , i.e. C ′ is a twin-cycle and cap∗ (C, v) ≥ cap(C ′ ) = 2. k ′ = 2: write AC ′ = {x, w}. The two ∅-free runs of C ′ have lengths a − 1 and |C ′ | − a − 1 for some a, so λC ′ ≥ ⌈|C ′ |/2⌉ − 1 = τC ′ and cap(C ′ ) ≥ 1. Let Gw be the branch of C ′ at w. Since w ∈ V (C ′ ) ⊆ V (Gv ) ∪ {v} and w ̸= x, we have w ∈ V (Gv ); moreover the component of G−w containing C ′ \{w} contains x and hence v, so v ∈ / V (Gw ) and therefore V (Gw ) ∪ {w} ⊆ V (Gv ). Consequently ℓG (Gw ) ≤ ℓG (Gv ) and C(C ′ , w) ⊆ C(C, v), while C′ ∈ / C(C ′ , w). As |V (Gw )| < |V (Gv )|, the induction hypothesis gives cap∗ (C ′ , w) ≥ 1 and hence cap∗ (C, v) ≥ cap(C ′ ) + cap∗ (C ′ , w) ≥ 2. k ′ ≥ 3: C ′ has two boundary vertices w1 ̸= w2 , both different from x. As above V (Gwi ) ∪ {wi } ⊆ V (Gv ), and Gw1 , Gw2 are disjoint because they are branches of the same cycle component at distinct boundary vertices; since w1 ∈ / V (Gw2 ) and w2 ∈ / V (Gw1 ), the sets C(C ′ , w1 ) and C(C ′ , w2 ) are disjoint as well. By the induction hypothesis cap∗ (C, v) ≥ cap∗ (C ′ , w1 ) + cap∗ (C ′ , w2 ) ≥ 2.

Y. Kim and Y. Sudo

XX:9

In all three cases cap∗ (C, v) ≥ 2, and Gv is not a beard because a beard contains no cycle and v would then lie on the single cycle C. The two cases together prove both assertions. ◀ ▶ Remark 18. Lemma 17 says that deactivating a boundary vertex costs at least one, and at least two unless its branch is a beard. Since the gain on a cycle component never exceeds 2 while one of its boundary vertices stays active (Lemma 23(iii)), deactivating a non-beard branch or two or more branches can never pay off; this is why only beard boundary vertices occur in Definition 13. The remaining case, in which all boundary vertices are deactivated, is handled quantitatively in Lemma 24.

3.4

The Canonical Set: the Lower Bound

∗ ▶ Definition 19 (Canonical set S ∗ ). For every latent twin-cycle C fix one witness vC (Definition 13), say the one of smallest index, and let zC be the leaf of the beard GvC∗ . For every unit-cycle C fix the ∅-free run PC with |PC | = λC = τC containing the vertex of smallest index among all such runs, and let uC be the vertex of smallest index in PC . For every ∗ twin-cycle (resp. latent twin-cycle) C let PC be the unique longest ∅-free (resp. {vC }-free) run, which is unique by Lemma 16, and let aC , dC be its two endpoints. We define   S∗ = x ∈ V : x is a leaf of G \ { zC : C latent twin-cycle }  [    [ ∪ {uC } ∪ {aC , dC } . C unit

C twin or latent twin

A boundary vertex v is called S ∗ -active if S ∗ ∩ V (Gv ) ̸= ∅, and S ∗ -inactive otherwise. ▶ Lemma 20. S ∗ ∩ A(G) = ∅ and |S ∗ | = cap(G). Moreover, a boundary vertex v is ∗ S ∗ -inactive if and only if v = vC for some latent twin-cycle C. Proof. Leaves of G are not articulation points; each uC lies on an ∅-free run and hence outside AC ; and aC , dC are not articulation points by Lemma 16. Hence S ∗ ∩ A(G) = ∅. The three sets forming S ∗ are pairwise disjoint: uC , aC , dC lie on a cycle and are not articulation points, so they have degree two in G and are not leaves, and each of them lies on exactly one cycle component, so no vertex is selected by two cycle components. For the cardinality, the map C 7→ zC is injective, since zC determines the beard containing it, which by (B2) is attached to exactly one cycle component, namely C. Therefore exactly nlt leaves are removed and
|S ∗ | = ℓ(G) − nlt + n1 + 2n2 + 2nlt = 2n2 + nlt + n1 + ℓ(G) = cap(G) by (2). ∗ For the last assertion, if v = vC then Gv is a beard whose only non-articulation-point ∗ ∗ vertex is zC ∈ / S , so S ∩ V (Gv ) = ∅. Conversely, let v be a boundary vertex of a cycle component C with S ∗ ∩ V (Gv ) = ∅. We first observe that no cycle component C ′ of positive capacity lies below (C, v): otherwise the vertices selected on C ′ (uC ′ , or aC ′ and dC ′ ) belong to S ∗ and are not articulation points, hence differ from v and lie in V (Gv ). By Lemma 17, cap∗ (C, v) ≥ 1, so Gv therefore contains a leaf x of G; as x ∈ / S ∗ , we have x = zC ′ for some latent twin-cycle C ′ , and B := GvC∗ ′ is the beard containing x. Since cap(C ′ ) = 1 > 0, the cycle C ′ does not lie below (C, v), i.e., V (C ′ ) ̸⊆ V (Gv ) ∪ {v}; as C ′ \ {v} is connected, this ∗ forces V (C ′ ) ∩ V (Gv ) = ∅ and in particular vC / V (Gv ). Now B is a path with endpoint ′ ∈ ∗ ∗ vC ′ , so B \ {vC ′ } is connected and contains x ∈ V (Gv ), hence is contained in V (Gv ) by (1); ∗ ∗ since vC ′ is adjacent to it and no vertex of Gv has a neighbour in Hv , we conclude vC ′ = v.

XX:10

A Maximum Mutual Visibility Set on a Cactus Graph

Finally v lies on no cycle other than C — a second cycle through v would lie below (C, v) and have positive capacity by Lemma 17 (case k ′ = 1 or k ′ = 2 of its proof) — so C ′ = C ∗ and v = vC . ◀ ▶ Lemma 21 (Local traversability). Let C be a cycle component of G and let X = S ∗ ∩ V (C). (T1) For any two S ∗ -active boundary vertices w, w′ of C, some shortest w–w′ arc of C avoids X. (T2) For every x ∈ X and every S ∗ -active boundary vertex w of C, some shortest x–w arc of C avoids X \ {x} in its interior. (T3) If |X| = 2, the two vertices of X are mutually visible with respect to S ∗ . Proof. By Definition 19, |X| ≤ 2, and |X| = 2 occurs exactly when C is a twin- or a latent twin-cycle, in which case X = {aC , dC } consists of the two endpoints of PC . (T3) is immediate: no vertex of S ∗ outside C lies on an arc of C, so both arcs joining the two vertices of X have interiors disjoint from S ∗ , and the shorter of them is a witness. If |X| ≤ 1, then (T2) is vacuous as well, because X \ {x} = ∅ means that every x–w arc qualifies. If C is a zero-cycle, (T1) is vacuous too since X = ∅. Let C be a unit-cycle, so X = {uC } with uC ∈ PC and |PC | = τC . For (T1), boundary vertices are articulation points and hence lie outside PC , so PC is contained in one of the two w–w′ arcs; that arc has length at least |PC | + 1 = τC + 1 ≥ |C|/2 (using |C| ≤ 2τC + 2), so the other arc, which avoids PC ∋ uC , is a shortest one. ∗ Finally let C be a twin-cycle or a latent twin-cycle, put XC = ∅ resp. XC = {vC }, and XC let λ = λC > τC be the length of PC , with X = {aC , dC } its endpoints. By Lemma 20, every S ∗ -active boundary vertex of C lies outside PC (the only boundary vertex that may ∗ lie on PC is vC , which is S ∗ -inactive). Let p (resp. q) be the vertex adjacent to aC (resp. dC ) outside PC . Note that λ ≥ τC + 1 ≥ |C|/2. For (T1), the arc containing PC has length at least λ + 1 > |C| − λ − 1, hence the complementary arc, which avoids PC ⊇ X, is strictly shorter.
For (T2) with x = aC , the two aC –w arcs have lengths 1 + δ and λ + |C| − λ − 1 − δ = |C|−1−δ, where δ = dC\PC (p, w). Since δ ≤ |C|−λ−1 ≤ |C|/2−1, we get 1+δ ≤ |C|−1−δ, so the first arc is a shortest one; its interior lies in C \ PC and therefore avoids dC . The case x = dC is symmetric. ◀ ▶ Proposition 22. S ∗ is an MVS of G, and consequently µ(G) ≥ cap(G) = 2n2 + nlt + n1 + ℓ(G). Proof. Let s, t ∈ S ∗ , s ̸= t. Since every boundary vertex is a cut vertex and no vertex of S ∗ is an articulation point (Lemma 20), the sequence of components of the cycle–tree decomposition visited by an s–t path is the same for every such path, and every s–t path is the concatenation of sub-paths joining consecutive boundary vertices inside single components. Consequently a concatenation of shortest sub-paths is a shortest s–t path, and it remains to choose each sub-path S ∗ -free, which is what Lemma 21 provides. Every boundary vertex v visited in this way is S ∗ -active, because s or t lies in Gv . Inside a tree component the sub-path is unique, and all its internal vertices are articulation points and hence not in S ∗ (Observation 11). Inside an intermediate cycle component C the sub-path joins two S ∗ -active boundary vertices of C; apply (T1). Inside the cycle component containing s (or t), the sub-path joins s (or t) to an S ∗ -active boundary vertex; apply (T2).

Y. Kim and Y. Sudo

If s and t lie in the same component, apply (T3) for a cycle component; for a tree component, both s and t are leaves of G by Observation 11 and the internal vertices of the connecting path avoid S ∗ by the same observation. Hence s and t are mutually visible with respect to S ∗ , and µ(G) ≥ |S ∗ | = cap(G) by Lemma 20 and (2). ◀

3.5

The Upper Bound and the Exact Formula

Throughout this subsection S denotes an arbitrary MVS of G with S ∩ A(G) = ∅. For a cycle component C we call v ∈ AC S-active if S ∩ V (Gv ) ̸= ∅ and S-inactive otherwise, and we write IC ⊆ AC for the set of S-inactive boundary vertices of C; thus λICC is the length of the longest run of C free of S-active boundary vertices. ▶ Lemma 23. Let C be a cycle component of G. Then |S ∩V (C)| ≤ 3, and (i) |S ∩V (C)| = 0 if λICC < τC ; (ii) |S ∩ V (C)| ≤ 1 if λICC = τC ; (iii) |S ∩ V (C)| ≤ 2 if λICC > τC and IC ̸= AC ; (iv) if |S ∩ V (C)| = 3 then IC = AC , i.e., every boundary vertex of C is S-inactive. Proof. By Observation 10, S ∩ V (C) is an MVS of the cycle C, so |S ∩ V (C)| ≤ 3 by Lemma 6. If IC = AC then λICC = |C| > τC and only statement (iv) is applicable, so assume AC \ IC ̸= ∅ for statements (i)–(iii). Let u ∈ S ∩ V (C); since u ∈ / A(G), the vertex u lies on some IC -free run P , delimited by two S-active boundary vertices p and q (with p = q and |P | = |C| − 1 > τC if |AC \ IC | = 1). If |P | < τC , then by Lemma 12 the arc through P is the unique shortest p–q path; picking sp ∈ S ∩ V (Gp ) and sq ∈ S ∩ V (Gq ) (which exist because p, q are S-active), every shortest sp –sq path passes through p, the arc, and q, hence through u ∈ S — contradicting mutual visibility of sp and sq . Thus every vertex of S ∩ V (C) lies on an IC -free run of length at least τC ; in particular (i) holds. Assume now λICC = τC . Suppose two vertices u = ̸ u′ of S ∩V (C) lay on two distinct IC -free ′ runs P ̸= P , necessarily both of length τC . Then |C| ≥ |P | + |P ′ | + |AC \ IC | ≥ 2τC + 2, and since |C| ≤ 2τC + 2 we get |C| = 2τC + 2 and AC \ IC = {p, q} with P, P ′ the two runs between p and q; the two p–q arcs both have length τC + 1 and each contains a vertex of S in its interior, so sp and sq are not mutually visible — a contradiction. Hence all vertices of S ∩ V (C) lie on one run P with |P | = τC , delimited by S-active p, q. If u, u′ ∈ P ∩ S with u closer to p, then by Lemma 12 the sub-path of P from p to u′ is the unique shortest p–u′ path and it passes through u, so sp and u′ are not mutually visible. Thus |S ∩ V (C)| ≤ 1, proving (ii). For (iv), suppose |S ∩ V (C)| = 3, say S ∩ V (C) = {u1 , u2 , u3 }, which splits C into three arcs. Let v ∈ AC ; then v ∈ / S, so v lies in the interior of one of the arcs, say the one joining u1 and u2 . Any shortest path from a vertex of Gv to u3 leaves Gv through v and then follows one of the two v–u3 arcs of C, which pass through u1 resp. u2 ; both are blocked. Hence S ∩ V (Gv ) = ∅, i.e., v is S-inactive. As v ∈ AC was arbitrary, IC = AC . Statement (iii) is the contrapositive of (iv) combined with |S ∩ V (C)| ≤ 3. ◀ ▶ Lemma 24 (Local exchange inequality). For every cycle component C of G, |S ∩ V (C)| ≤ P cap(C) + v∈IC cap∗ (C, v). Proof. If IC = ∅, then λICC = λC and Lemma 23 gives |S ∩ V (C)| ≤ 2 if C is a twin-cycle, ≤ 1 if C is a unit-cycle, and = 0 otherwise, which is at most cap(C) in all four cases (for a latent twin-cycle λC < τC , so the left-hand side is 0 ≤ 1 = cap(C)). P Let IC ̸= ∅ and put κ = v∈IC cap∗ (C, v). By Lemma 17, κ ≥ |IC |, and κ ≥ |IC | + 1 if some branch Gv with v ∈ IC is not a beard.

XX:11

XX:12

A Maximum Mutual Visibility Set on a Cactus Graph

If |S ∩V (C)| = 3, then IC = AC by Lemma 23(iv). If |AC | = 1, then λC = |C|−1 > τC , so cap(C) = 2, while κ ≥ 1 by Lemma 17; hence cap(C) + κ ≥ 3. If |AC | = 2, then λC ≥ τC by the computation in the proof of Lemma 17, so cap(C) ≥ 1 and cap(C) + κ ≥ 1 + 2 = 3. If |AC | ≥ 3, then κ ≥ 3. If |S ∩ V (C)| = 2, then λICC > τC by Lemma 23(i)–(ii). If |IC | ≥ 2, then κ ≥ 2. If IC = {v} and Gv is not a beard, then κ ≥ 2. If IC = {v} and Gv is a beard, then v is a beard boundary vertex with λvC > τC ; hence C is a twin-cycle, a unit-cycle, or — if λC < τC — a latent twin-cycle, so cap(C) ≥ 1 and cap(C) + κ ≥ 1 + 1 = 2. If |S ∩ V (C)| ≤ 1, the inequality holds because κ ≥ |IC | ≥ 1. ◀ The last ingredient is a bookkeeping statement which guarantees that, when the local inequality of Lemma 24 is summed over all cycle components, no leaf and no cycle component is counted twice. ▶ Lemma 25. Let S ̸= ∅ be an MVS of G with S ∩ A(G) = ∅ and let W be the set of ⊆-maximal members of {Gv : v is S-inactive}. Then: (i) the family {Gv : v is S-inactive} is laminar; consequently the members of W are pairwise disjoint, and each H ∈ W equals GvH for a unique boundary vertex vH ; (ii) calling a cycle component C ′ below H when V (C ′ ) ⊆ V (H) ∪ {vH }, no cycle component is below two distinct members of W, and every cycle component below some H ∈ W satisfies S ∩ V (C ′ ) = ∅; (iii) if a cycle component C is below no member of W and v ∈ IC , then Gv ∈ W, and the map (C, v) 7→ Gv is injective on such pairs; P (iv) for H = Gv as in (iii), cap∗ (C, v) = ℓG (H) + C ′ below H cap(C ′ ). Proof. (i) Laminarity. Let Gv (a branch of C) and Gv′ (a branch of C ′ ) be S-inactive. We show that if they are neither disjoint nor nested, then V (Gv ) ∪ V (Gv′ ) ⊇ V \ {z} for some z ∈ A(G); since S avoids both branches and A(G), this forces S = ∅, a contradiction. If v = v ′ (so C = ̸ C ′ ), let K1 , . . . , Km be the components of G − v with C \ {v} ⊆ K1 and S S ′ C \{v} ⊆ K2 ; then Gv = i̸=1 Ki and Gv′ = i̸=2 Ki , whose union is V \{v}, and v ∈ A(G). Let now v ̸= v ′ . If v ′ ∈ / V (Gv ) and v ∈ / V (Gv′ ), then v ′ ∈ V (Hv ) by (1), so Gv ∪ {v} is connected in G − v ′ and hence contained in the component of G − v ′ containing v; that component is disjoint from Gv′ , so Gv ∩Gv′ = ∅. Otherwise, say v ′ ∈ V (Gv ), and let K be the component of G − v containing v ′ , so K ⊆ Gv . Every component of G − v ′ either contains v or is contained in K. If Gv′ consists only of components of the latter kind, then Gv′ ⊆ K ⊆ Gv and the two branches are nested. Otherwise Gv′ contains the component L ∋ v of G − v ′ , and L ⊇ V \ (K ∪ {v ′ }); together with Gv ⊇ K this gives V (Gv ) ∪ V (Gv′ ) ⊇ V \ {v ′ } with v ′ ∈ A(G). Consequently the maximal members of a laminar family are pairwise disjoint. Finally, each H ∈ W determines its boundary vertex: if v = ̸ v ′ satisfied Gv = Gv′ = H, then every component K of H would be simultaneously a component of G − v and of G − v ′ , so its only neighbour outside K would be both v and v ′ , which is impossible; and if v = v ′ but the two branches came from different cycles C ̸= C ′ , then the branch of C at v would contain C ′ \ {v} while the branch of C ′ at v would not. (ii) If a cycle component C ′ were below two distinct H, H ′ ∈ W, then, since V (H)
∩ ′ ′ ′ / V (H ) by (1), we would get V (C ) ⊆ V (H ′ ) = ∅, vH ∈ V (H) ∪ {vH } ∩
/ V (H) and vH ∈ ′ ′ ′ V (H ) ∪ {vH ′ } ⊆ {vH , vH ′ }, contradicting |V (C )| ≥ 3. If C is below H, then V (C ′ ) ⊆ V (H) ∪ {vH }, and S avoids V (H) as well as vH ∈ A(G), so S ∩ V (C ′ ) = ∅. (iii) Let C be below no member of W and v ∈ IC . By maximality, Gv ⊆ H for some H ∈ W. Suppose the inclusion is strict. By the case analysis in (i), vH ∈ / V (Gv ) and

Y. Kim and Y. Sudo

XX:13

Figure 3 A maximum mutual visibility set of the given cactus graph (µ(G) = 24)

v∈ / V (H) would give Gv ∩ H = ∅, which is impossible as Gv = ̸ ∅; and vH ∈ V (Gv ) would give H ⊆ Gv or S = ∅. Hence v ∈ V (H), and v = ̸ vH . The set C \ {vH } is connected (it is C itself or a path) and contains v ∈ V (H), so it is contained in the component of G − vH containing v, which is part of H; therefore V (C) ⊆ V (H) ∪ {vH }, i.e., C is below H — a contradiction. Thus Gv ∈ W. For injectivity, if v = v ′ and C = ̸ C ′ are two such cycle components with v ∈ IC ∩ IC ′ , then C ′ \ {v} is contained in the branch of C at v, so C ′ is below Gv ∈ W, which is excluded; and if v ̸= v ′ then Gv ̸= Gv′ by (i). (iv) By (i) we have v = vH for H = Gv , so C(C, v) = {C ′ : V (C ′ ) ⊆ V (H) ∪ {vH }} is exactly the set of cycle components below H, and the claim is Definition 15. ◀ ▶ Theorem 26. Let G be a cactus graph that is not a simple cycle. Then µ(G) = cap(G) = 2n2 + nlt + n1 + ℓ(G). Proof. The inequality µ(G) ≥ cap(G) is Proposition 22. For the converse, let S be a maximum MVS with S ∩ A(G) = ∅, which exists by Lemma 7 and is non-empty. Every vertex of V \ A(G) lies in exactly one component of the cycle–tree decomposition, so P P |S| = C |S ∩ V (C)| + T |S ∩ V (T )|, where C ranges over cycle components and T over tree components; by Observation 11, S ∩ V (T ) consists of leaves of G. Let W be as in S Lemma 25. As S avoids W and the members of W are pairwise disjoint, X X X |S ∩ V (T )| ≤ ℓ(G) − ℓG (H), |S ∩ V (C)| = 0. T

H∈W

C below some H

By Lemma 25(iii)–(iv), summing Lemma 24 over the cycle components that are below no member of W contributes each H ∈ W at most once, with cap∗ (C, v) = ℓG (H) + P ′ C ′ below H cap(C ). Hence   X X X |S| ≤ cap(C) + cap∗ (C, v) + ℓ(G) − ℓG (H) v∈IC

C below no H

≤

X C below no H

=

X

cap(C) +

X H∈W

H∈W

ℓG (H) +

X

cap(C ′ )



+ ℓ(G) −

C ′ below H

cap(C) + ℓ(G) = cap(G) = 2n2 + nlt + n1 + ℓ(G).

X

ℓG (H)

H∈W

◀

C∈C(G)

Figure 3 shows a maximum mutual visibility set of the given cactus graph, µ(G) = 24. ▶ Corollary 27. For every cactus graph G that is not a simple cycle, µ(G) ≤ 2|C(G)| + ℓ(G), and equality holds if and only if every cycle component of G is a twin-cycle.

XX:14

A Maximum Mutual Visibility Set on a Cactus Graph

Proof. By Definition 14 we have cap(C) ≤ 2 for every cycle component, with equality if and only if C is a twin-cycle; now apply Theorem 26 and (2). ◀ ▶ Corollary 28. A maximum MVS of a cactus graph G on n vertices, and hence µ(G), can be computed sequentially in O(n) time. Proof. The blocks and the articulation points of G are computed by one depth-first search in O(n + |E|) = O(n) time, since |E| ≤ 32 (n − 1) in a cactus; this yields the cycle–tree decomposition of Definition 3. Traversing each cycle component C once gives |C|, τC , all maximal ∅-free runs, λC and, for each boundary vertex v, the value λvC = max{λC , αv +1+βv }; P P the total cost is O( C |C|) = O(n) by the bound C |C| ≤ n+|C(G)|−1. One traversal of the tree components identifies the beards and their boundary vertices, after which Definition 13 classifies every cycle component and Definition 19 selects the vertices of S ∗ , both in O(n) time. Correctness is Theorem 26 and Proposition 22. ◀ ▶ Remark 29. Cactus graphs and block graphs (every block a clique) properly overlap without either containing the other, and the MVN of block graphs is already known [21]; the two analyses are nevertheless of a different nature. In a block graph every block has diameter one, so any two vertices of a block are mutually visible regardless of the rest of the set and the analysis is governed by the cut-vertex structure alone. In a cactus a cycle block has diameter ⌊|C|/2⌋, so distances inside a block matter and a chosen vertex may destroy the visibility of two vertices of the same block—which is precisely what the comparison of λC with τC measures, and which has no counterpart for cliques, as has the latent twin-cycle. ▶ Remark 30. Lemma 23 cannot be strengthened to “|S ∩V (C)| = cap(C) for every maximum MVS S”. For the 5-cycle p, w1 , w2 , q, r whose only articulation points are p and q, each carrying a pendant leaf a resp. b, we have λC = τC = 2 and µ(G) = 3, yet both {a, b, w1 } and {a, w1 , r} are maximum MVSs and the latter takes two vertices of C while omitting b. This is why we combine an upper bound (Lemma 24) with an explicit construction (Definition 19).

4

Self-Stabilizing Algorithms for a Maximum Mutual Visibility Set

By Theorem 26, a maximum MVS is determined by the cycle–tree decomposition of G together with the type of each cycle component, and Definition 19 turns this classification into an explicit maximum MVS S ∗ . Both algorithms below compute exactly S ∗ , so their correctness follows from Theorem 26 and Proposition 22 once they are shown to evaluate Definition 19 correctly. Only two of its choices are not already unique, and both are resolved with process identifiers: for a unit-cycle there may be up to two ∅-free runs of length λC , exactly one of which hosts the single MVS vertex; and a latent twin-cycle may have several witnesses, exactly one of which may be deactivated, since deactivating a second one would forfeit a further leaf without any gain. For a twin-cycle no symmetry breaking is needed, the longest ∅-free run being unique (Lemma 16). The two algorithms share this correctness argument and differ only in their optimization criterion: Algorithm 1 (Section 4.2) uses a single BFS tree and is space-efficient, whereas Algorithm 2 (Section 4.5) uses parallel BFS trees from all high-degree vertices and stabilizes in time proportional to the largest component rather than to the diameter. Section 4.1 fixes the computational model and the specification of the task. Section 4.2 describes the strategy of Algorithm 1 in four phases, Section 4.3 turns that strategy into a complete set of rules in the state-reading model, and Section 4.4 proves its correctness and its complexity. Section 4.5 obtains Algorithm 2 from Algorithm 1 by replacing the single BFS

Y. Kim and Y. Sudo

tree by a family of local ones, and proves the matching lower bound; Section 4.6 compares the two algorithms.

4.1

System Model and Specification

Network and communication. The system is modeled by a cactus graph G = (V, E) that is neither a simple cycle nor a simple path (for those topologies a maximum MVS is trivial), where each vertex is a process and each edge a bidirectional communication link. We adopt the state reading (shared memory) model: each process v reads its own variables and those of all u ∈ N (v), and is a state machine whose next state is a function of these. Each process v has a distinct identifier id(v) taken from a domain of size nO(1) , and every process knows a common upper bound N ≥ n on the number of processes; all distance variables range over the finite domain {0, 1, . . . , N }, and a value read outside this domain is treated as N . Both assumptions are standard and necessary here: with an unbounded distance domain the space complexity could not be bounded by any function of n, and with arbitrary integers as initial values the stabilization time would depend on the magnitude of the corruption rather than on the topology. There is one predetermined leader r with δ(r) ≥ 3; such a vertex always exists in our topologies. Executions and the daemon. A configuration γ = (sv )v∈V is the tuple of all process states. Each process has a finite set of rules, each of the form yv ← F (·) where F depends only on the state of v and of its neighbours; a process is enabled in γ if the value of one of its variables differs from the value prescribed by the corresponding rule, and executing a step means that all rules of the process are applied simultaneously. We assume the distributed daemon: at each step an arbitrary non-empty subset of the enabled processes executes simultaneously. An execution is a maximal sequence γ0 , γ1 , . . . of configurations linked by steps; no assumption is placed on γ0 , which models arbitrary transient faults (the code itself is incorruptible). We further assume the daemon to be weakly fair: a process that remains continuously enabled eventually executes a step. This assumption is what makes a round-based complexity measure meaningful—an unfair daemon may starve one process forever, so no algorithm admits a bound in rounds under it—and it is the standard assumption in the literature whenever stabilization time is measured in rounds. The first round of an execution is its shortest prefix in which every process enabled in γ0 either executes a step or becomes disabled; the rounds of the remaining suffix are defined inductively. Output, specification and legitimacy. Every process v has a boolean output variable inMVSv , and the output of a configuration γ is O(γ) = {v ∈ V | inMVSv = true}. The maximum-MVS construction task requires that O(γ) be a maximum MVS of G containing no articulation point of G; by Lemma 7 this restriction is without loss of generality, and it makes the specification a function of G alone. A configuration is legitimate if no process is enabled in it. Thus legitimacy is a purely local, syntactic predicate; it is not defined in terms of the output. That the two coincide is a theorem, proved in Section 4.4: the rules of Algorithm 1 admit exactly one legitimate configuration, and its output is the maximum MVS S ∗ of Definition 19 (Theorem 37). An algorithm is self-stabilizing for the task if every execution contains a legitimate configuration, and silent if no variable changes once a legitimate configuration is reached; since a legitimate configuration is by definition a fixed point of the rules, both of our algorithms are silent, and the output is constant from that point on.

XX:15

XX:16

A Maximum Mutual Visibility Set on a Cactus Graph

4.2

Algorithm 1: A Space-Efficient Self-Stabilizing Algorithm

Algorithm 1 evaluates Definition 19 using a single-root BFS tree, in four phases. Phase 1 (BFS tree). A single BFS tree Br rooted at the leader r is constructed by the classical distance-plus-one rule; self-stabilizing BFS constructions with a designated root go back to Huang and Chen [17] and to Dolev, Israeli and Moran [14] (see also [11, Ch. 2]). So that the paper is self-contained and so that the round complexity does not depend on the variant chosen, we state and prove the bound we use in Lemma 33 of Section 4.3: with the distance domain {0, . . . , N } and the root pinned to 0, the construction stabilizes in O(D) rounds under the distributed daemon. Phase 2 (cycle identification and articulation points). Because the cycles of a cactus are edge-disjoint, every cycle of C(G) contains exactly one non-tree edge of Br and, conversely, the fundamental cycle of a non-tree edge is a cycle of C(G); and {u, v} is a non-tree edge exactly when paru ̸= v and parv = ̸ u, which both endpoints check locally. We therefore name the cycle containing eC = {a, b} by cid(C) = (min{id(a), id(b)}, max{id(a), id(b)})—an identifier that needs no prior knowledge of V (C)—and establish its membership by one leaf-to-root wave along Br , at the end of which the vertex xC = lca(a, b) of minimum depth computes |C| = dista + distb − 2 distxC + 1 and τC and broadcasts them back down; see Section 4.3 for the rules and their analysis. Articulation points need no DFS low-link computation: in a cactus a vertex of degree at least three is always an articulation point, and a vertex of degree two is one exactly when it lies on no cycle. Phase 3 (λC , λvC and beard detection). For each cycle C the parameter λC is computed by propagating run-length information around C, and each boundary vertex v of C additionally computes the lengths αv , βv of the two ∅-free runs adjacent to it and stores λvC = max{λC , αv + 1 + βv }, the value of λC obtained by deactivating v alone. Beard detection is a leaf-to-root propagation along Br : each leaf sends upward the maximum number of children seen so far, and a tree component T is flagged as a beard iff that count never exceeds one along the whole path to the boundary vertex (no branching in T ) and that boundary vertex belongs to exactly one cycle, as required by (B2). A beard boundary vertex v is deactivated only when λC < τC and λvC > τC , i.e., only when C is a latent twin-cycle with witness v; deactivating a beard unconditionally would forfeit its leaf without any gain, for instance when λC = τC already. Among several witnesses, only the one of smallest ID is deactivated. Phase 4 (classification and selection). Each cycle is classified from λC , λvC and τC (Definition 13), and each process sets inMVSv exactly as prescribed by Definition 19: the two endpoints of the unique longest run for a twin- or latent twin-cycle (Lemma 16); one vertex of one run of length τC for a unit-cycle, the tie between the at most two such runs being broken by ID; nothing for a zero-cycle; every leaf of G except those whose beard boundary vertex was deactivated in Phase 3.

4.3

The Rules of Algorithm 1

The description of Section 4.2 is a description of a strategy: it says which quantity is computed in each phase, but it leaves the phrases “propagating run-length information around C” and “a leaf-to-root propagation along Br ” informal, and in a self-stabilizing setting such phrases hide exactly the two questions that matter, namely what a process does when the data it reads are corrupted, and how many rounds an aggregation costs. This section removes that informality: it gives the complete set of rules of Algorithm 1, together with the analysis tool (Lemma 31) that converts each aggregation into an explicit round bound.

Y. Kim and Y. Sudo

We work in the state-reading model, in which a process may read only its own variables and
those of its neighbours. Every rule is a total assignment yv ← F local topology of v, {yu′ }u∈N (v) whose right-hand side depends only on variables of v and of its neighbours; a process is enabled whenever one of its variables differs from the value prescribed by its rule, and it executes all of its rules when activated. No rule is conditional on the current value of the variable it assigns, so an arbitrary initial value is always overwritten rather than preserved; this, together with the finiteness of every variable domain, is what purges corrupted states, and it is also why the algorithm is silent.

A layered evaluation lemma All computations are organised into layers. A layer consists of one variable per process (or per cycle incidence, see the list of variables below) together with an evaluation order: an acyclic orientation of a subgraph of G such that, within the layer, the rule of a process depends only on its in-neighbours. The depth of a layer is the length of the longest directed path of its evaluation order. The following lemma is stated in a per-variable form. The reason is that the analysis of Algorithm 2 (Section 4.5) needs to conclude that some variables are stable after few rounds even though the system as a whole is not; a lemma that only bounds the global stabilization time cannot give that. ▶ Lemma 31 (Layered evaluation). Let y 1 , . . . , y k be layers such that the rule of yvi depends only on the local topology of v, on yuj for j < i and u ∈ N (v) ∪ {v}, and on yui for the in-neighbours u of v in the evaluation order of layer i. For a variable instance y = yvi define its dependency depth ∆(y) to be 0 if the rule of y refers to no other variable of the family, and 1 + max ∆(y ′ ) over the variables y ′ that the rule of y refers to otherwise; the recursion is well founded because the dependency relation is acyclic. Write π(y) for the value that the rule of y prescribes when all the variables it refers to hold their own prescribed values. Then, under the weakly fair distributed daemon and from every initial configuration, every execution satisfies: for every variable instance y, from the end of round ∆(y) + 1 onwards, y = π(y). Pk In particular every variable holds its prescribed value after at most 1 + i=1 (hi + 1) rounds, where hi is the depth of layer i, and no process is enabled from that point on. Proof. Recall that a process is enabled in a configuration precisely when at least one of its variables differs from the value its rule prescribes in that configuration, that a step recomputes all the variables of the process at once, and that, by the definition of a round, a process that is enabled at the beginning of a round either executes a step during that round or becomes disabled during it. We induct on ∆(y); let p be the process owning y. Let ∆(y) = 0. The right-hand side of the rule of y is a function of the local topology of p alone, hence is constant along the execution and equal to π(y). During round 1, either p executes a step — after which y = π(y) — or p becomes disabled, which by definition means that all of its variables, y included, already agree with the prescribed values. Every later step of p re-assigns the same constant, so y = π(y) from the end of round 1 on. Let ∆(y) = d > 0 and assume the claim for every variable of dependency depth less than d. Every variable that the rule of y refers to has dependency depth at most d − 1 and therefore holds its prescribed value from the end of round d on. Consequently, from the end of round d onwards the right-hand side of the rule of y evaluates to π(y) and does not change any more. The argument of the base case, applied to round d + 1, then gives y = π(y) from the end of round d + 1 on.

XX:17

XX:18

A Maximum Mutual Visibility Set on a Cactus Graph

For the global bound, a variable of layer i that sits at position h of the evaluation order of P Pk that layer has dependency depth at most j<i (hj +1)+h, whence maxy ∆(y) ≤ i=1 (hi +1). Once every variable holds its prescribed value, no process is enabled by definition. ◀ ▶ Corollary 32 (Local stabilization). Under the hypotheses of Lemma 31, a set Y of variable instances with maxy∈Y ∆(y) = O(k) holds its prescribed values after O(k) rounds, whatever the dependency depths of the remaining variables are. Lemma 31 is the tool that replaces informal phrases such as “propagated within C”: each aggregation below is realised as an explicit layer with an explicit evaluation order, an explicit depth, and an explicit purge behaviour.

Notation and variables We write N (v) for the neighbours of v, δ(v) = |N (v)|, ch(v) = {u ∈ N (v) | paru = v} for the children of v in Br , and Evnt = {u ∈ N (v) | paru ̸= v∧parv ̸= u},

key(v, u) = min{id(v), id(u)}, max{id(v), id(u)}

for the non-tree neighbours of v and the identifier of the cycle closed by such an edge. A process stores a constant part and one record per incident cycle; Recv is the set of identifiers for which v holds a record and zv [c] is field z of record c. This per-incidence representation is what allows a process on γv ≥ 2 cycles—for instance the centre of a friendship graph—to keep two cycle identifiers, two pairs of cycle neighbours and two values of λC at the same time. parv , distv isAPv , chainv , deAbvv , inMVSv Srcv [c], srcv [c], upv [c], botv [c] distxv [c], sizev [c], tauv [c] arm0v [c], armv [c], posv [c] lrunv [c], rrunv [c], runv [c] pmaxv [c], Lamv [c] alphav [c], betav [c], lamDev [c] bBndv [c], witv [c] wminv [c], wposv [c], deactv [c] lrun′v [c], . . . , Lam′v [c] fminv [c], fposv [c] cyctypev [c], selv [c]

parent and depth in Br , distv ∈ {0, . . . , N } booleans sources of c, their number, forwarding flag, depth of the endpoint below distxC , |C|, τC source labelled arm 0, side of C, position along C run lengths to the left, to the right, and in total running maximum of run, and λC the two adjacent runs, and λvC beard boundary flag, witness flag witness selection along C the five run variables recomputed after deactivation first position at which a longest run starts type of C, and selection predicate

Every field is an identifier pair, a value of {0, . . . , N }∪{∞}, or a constant-size flag, so a record occupies O(log n) bits. In an arbitrary configuration v holds at
most |Candv | ≤ δ(v) records (the rule for Candv in Algorithm 1), hence
O (δ(v) + 1) log n bits, and after stabilization P exactly γv records, hence O (γv + 1) log n bits; since v δ(v) = 2|E| = O(n) in a cactus, both bounds give a total of O(n log n) bits and an average of O(log n) bits per process, as established in Proposition 39.

Layers 1–2: BFS tree and cycle identification An edge {u, v} is a non-tree edge of Br exactly when paru ̸= v and parv = ̸ u, which both endpoints check locally. Because the cycles of a cactus are edge-disjoint, each cycle contains

Y. Kim and Y. Sudo

XX:19

Algorithm 1 Rules for process v — Layer 1 (BFS tree) and Layer 2 (cycle identification)

Layer 1 (BFS tree; evaluation order: Br from the root, depth ≤ D) 1: if v = r then 2: parv ← ⊥; distv ← 0 3: else
4: parv ← arg min min{dist , N }, id(u) u u∈N (v)  5: distv ← min min{distparv , N } + 1, N ▷ finite domain: out-of-range values are read as N 6: end if Layer 2 (cycle identification; evaluation order: Br from the leaves, depth ≤ D) 7: Candv ← {key(v, u) | u ∈ Evnt } ∪

S

u∈ch(v) {c ∈ Recu | upu [c]}

▷ at most δ(v) candidates

8: for all c ∈ Candv do

 Srcv[c] ← (⊥, distv ) | ∃u ∈ Evnt : key(v, u) = c ⊎ (u, botu [c]) | u ∈ ch(v), c ∈ Recu , upu [c] 10: end for 11: Recv ← { c ∈ Candv | |Srcv [c]| ≤ 2 } ▷ |Srcv [c]| ≥ 3 is impossible in a cactus: purge 12: for all c ∈ Recv do 13: srcv [c] ← |Srcv [c]|; upv [c] ← (srcv [c] = 1) 14: if srcv [c] = 1 then botv [c] ← β where Srcv [c] = {(·, β)} else botv [c] ← ⊥ 15: end for 9:

exactly one non-tree edge and, conversely, the fundamental cycle of a non-tree edge is a cycle of C(G); naming C after its non-tree edge therefore requires no prior knowledge of V (C) and removes the circularity inherent in naming a cycle after its minimum-depth vertex. ▶ Lemma 33 (Pinned BFS). Consider the rule distρ = 0 and, for v ̸= ρ, distv ← min{minu∈N (v) distu + 1, N } over the domain {0, . . . , N }, a value read outside the domain counting as N . From every initial configuration, and under the weakly fair distributed daemon, the following holds for every k ≥ 0: at the end of round k + 1 we have distv = dG (ρ, v) for every v with dG (ρ, v) ≤ k, and the parent pointers of those vertices are correct one round later. In particular all distances are correct after D + 1 rounds; and the distances inside the ball of radius k around ρ are correct after k + 1 rounds whatever the diameter of G is. Proof. Write d(v) = dG (ρ, v). Upper direction. We show by induction on ρ′ that, from the end of round ρ′ on, distv ≤ d(v) holds for every v with d(v) ≤ ρ′ − 1. For ρ′ = 1 this concerns only v = ρ, whose rule pins distρ = 0; during round 1 the process ρ either executes or is disabled, so the value is 0 at the end of round 1 and never changes again. Assume the property after round ρ′ and let d(v) = ρ′ . The vertex v has a neighbour u with d(u) = ρ′ − 1, and distu ≤ d(u) holds throughout round ρ′ + 1 by the induction hypothesis and by the fact that the property is preserved by every step: a process w with d(w) ≤ ρ′ − 1 that executes sets distw ≤ distu′ + 1 ≤ d(u′ ) + 1 = d(w) for a neighbour u′ on a shortest ρ–w path. Hence during round ρ′ + 1 the process v either executes, and then distv ≤ distu + 1 ≤ d(v), or is disabled, in which case its value already equals the one its rule prescribes, which is at most d(v) for the same reason. Lower direction. The property “distv ≥ min{d(v), ρ′ } for every v” is preserved by every step, because a process that executes sets distv ≥ min{minu∈N (v) min{d(u), ρ′ } + 1, N } = min{d(v), ρ′ + 1} ≥ min{d(v), ρ′ }, using minu∈N (v) d(u) = d(v) − 1 and d(v) ≤ D ≤ N .

XX:20

A Maximum Mutual Visibility Set on a Cactus Graph

We show by induction on ρ′ that it holds at the end of round ρ′ ; it is vacuous for ρ′ = 0. Assume it after round ρ′ . Every process either executes at some point of round ρ′ + 1, and the displayed computation then gives distv ≥ min{d(v), ρ′ + 1}, or is disabled at some point of that round, in which case its value equals the one prescribed by its rule and the same computation applies; and the bound survives the remaining steps of the round by the preservation property. Conclusion. At the end of round k + 1 and for v with d(v) ≤ k, the upper direction gives distv ≤ d(v) and the lower direction gives distv ≥ min{d(v), k + 1} = d(v). The parent rule is a function of the distances of the neighbours of v, all of which are at distance at most d(v) + 1 from ρ, so it is correct one round later. ◀ ▶ Lemma 34. After Layers 1–2 have stabilized, for every C ∈ C(G) with non-tree edge eC = {a, b} and c = cid(C) = key(a, b) we have {v | c ∈ Recv } = V (C); moreover srcv [c] = 2 exactly for v = xC := lca(a, b), the vertex of C of minimum depth, and SrcxC [c] contains the two values dista and distb . No identifier is held by a vertex outside the corresponding cycle. Proof. V (C) is the union of the tree paths a ⇝ xC and b ⇝ xC together with eC . A vertex strictly inside one of these paths has exactly one child carrying c and is not an endpoint of eC , so |Src| = 1; each of a, b has an anchor and no child carrying c unless it equals xC ; and xC receives c from its two distinct children on the two paths or—when xC ∈ {a, b}—from one child and from its own anchor, so |Src| = 2 in either case. Forwarding stops exactly at xC , so no vertex outside V (C) obtains c, and bot copies the depth of the endpoint at the bottom of each chain upward unchanged. Finally c ∈ Candv requires an anchor or a forwarding child, so a fabricated identifier disappears in one round. ◀ ▶ Example 35. Let C be the 4-cycle v a b c with a pendant leaf at v and r = v, so that the stabilized depths are 0, 1, 2, 1. The unique non-tree edge is {b, c} and c = key(b, c); the wave travels b → a → v and c → v, and v has |Srcv [c]| = 2, so xC = v and all four vertices hold the record, with size = 2 + 1 − 2 · 0 + 1 = 4 by the rule for size in Algorithm 2. Under a naming scheme based on the minimum-depth vertex of C the wave could not even have been started, since xC is precisely what the wave computes.

Layers 3–4: cycle geometry and articulation points A direct computation from Lemma 34 shows that pos enumerates V (C) as w0 = xC , w1 , . . . , w|C|−1 along C, consecutive positions being adjacent—the positions β0 − distxC and β0 − distxC + 1 being joined by eC itself—so that prv and nxt are well defined and are the two neighbours of v on C. Note that |C| is obtained arithmetically from three BFS depths; at no point does a rule range over “all vertices carrying the same identifier”. ▶ Lemma 36. xC is an articulation point of G; consequently no run of C contains w0 , and the runs of C are intervals of the path w1 , . . . , w|C|−1 . Proof. If r ∈ / V (C) then xC separates C from r; if r ∈ V (C) then xC = r and δ(r) ≥ 3, which in a cactus forces r to be an articulation point. ◀

Layers 5–8: runs and λC By Lemma 36 the recursions of Layers 5–7 are grounded at w0 , so they are genuine path evaluations and runv [c] is the length of the run of C containing v. The global maximum λC is obtained as a running maximum and is read by xC from its neighbour at position |C| − 1, then broadcast downwards; no other form of aggregation is used.

Y. Kim and Y. Sudo

XX:21

Algorithm 2 Rules for process v — Layer 3 (geometry of C) and Layer 4 (articulation points)

Layer 3 (evaluation order: Br from the root, depth ≤ D) 1: for all c ∈ Recv do 2: if srcv [c] = 2 then ▷ v = xC
3: let Srcv [c] = {(σ0 , β0 ), (σ1 , β1 )} ordered by βi , id(σi ) , with id(⊥) := −∞ 4: distxv [c] ← distv ; sizev [c] ← β0 + β1 − 2 distv + 1; tauv [c] ← ⌊(sizev [c] − 1)/2⌋ 5: arm0v [c] ← σ0 ; armv [c] ← ⊥; posv [c] ← 0 6: else 7: p ← parv 8: distxv [c] ← distxp [c]; sizev [c] ← sizep [c]; tau
v [c] ← taup [c] 9: if srcp [c] = 2 then armv [c] ← arm0p [c] = v ? 0 : 1 else armv [c] ← armp [c]
10: posv [c] ← distv − distxv [c] if armv [c] = 0, else sizev [c] − distv − distxv [c] 11: end if 12: prvv [c] ← the u ∈ N (v) with c ∈ Recu and posu [c] ≡ posv [c] − 1 (mod sizev [c]) 13: nxtv [c] ← the u ∈ N (v) with c ∈ Recu and posu [c] ≡ posv [c] + 1 (mod sizev [c]) 14: end for Layer 4 (local)

15: isAPv ← δ(v) ≥ 3 ∨ δ(v) = 2 ∧ Recv = ∅

Layers 9–13: beards, witnesses and deactivation The clause posv [c] ̸= 0 ∨ v = r in the rule for bBnd excludes xC ̸= r, whose branch contains r and is therefore not a beard; the clause δ(v) = 3 together with |Recv | = 1 encodes (B2), and chainu encodes (B1) and (B3). Selecting the witness of smallest position rather than of smallest identifier makes the tie-break depend only on the leader and on Br .

Layers 14–15: classification and output For a twin- or latent twin-cycle the two selected vertices are the two endpoints of the unique longest deactivated run (Lemma 16), which are exactly the vertices of that run with lrun′ = 1 ∗ or rrun′ = 1; the witness vC itself is excluded by ¬isAPv , and is in any case internal to the run by Lemma 16. For a unit-cycle, the rule for fmin marks the first vertex of a longest run Algorithm 3 Rules for process v — Layers 5–8 (runs, λC ) 1: for all c ∈ Recv do

Layer 5 (order: C by increasing pos, depth ≤ |C|) lrunv [c] ← 0 if isAPv ∨ posv [c] = 0, else 1 + lrunprvv [c] [c] Layer 6 (order: C by decreasing pos, depth ≤ |C|) 3: rrunv [c] ← 0 if isAPv ∨ posv [c] = 0, else 1 + rrunnxtv [c] [c] 4: runv [c] ← lrunv [c] + rrunv [c] − 1 if ¬isAPv ∧ posv [c] ≥ 1, else 0 Layer 7 (order: C by increasing pos,  depth ≤ |C|) 5: pmaxv [c] ← 0 if posv [c] = 0, else max runv [c], pmaxprvv [c] [c] Layer 8 (order: Br from the root, depth ≤ D) 6: Lamv [c] ← pmaxprvv [c] [c] if posv [c] = 0, else Lamparv [c] ▷ prv of xC is w|C|−1 7: end for

2:

XX:22

A Maximum Mutual Visibility Set on a Cactus Graph

Algorithm 4 Rules for process v — Layers 9–13 (beards, witnesses, deactivation)

Layer 9 (order: Br from the leaves, depth ≤ D) 1: chainv ← true if δ(v) = 1; else if Recv = ∅ ∧ δ(v) = 2 ∧ |ch(v)| = 1 then chainv ← chainu for the unique u ∈ ch(v); else chainv ← false 2: TCv ← {u ∈ ch(v) | ∀c ∈ Recv ∩ Recu : u ∈ / {prvv [c], nxtv [c]}} ▷ tree children of v Layers 10–11 (local, then C by increasing pos and Br from the root) 3: for all c ∈ Recv do

bBndv [c] ← |Recv | = 1 ∧ δ(v) = 3 ∧ |TCv | = 1 ∧ chainu ∧ posv [c] ̸= 0 ∨ v = r , TCv = {u} 5: alphav [c] ← runprv  v [c] [c]; betav [c] ← runnxtv [c] [c] 6: lamDev [c] ← max Lamv [c], alphav [c] +
1 + betav [c] ▷ = λvC
7: witv [c] ← bBndv [c] ∧ Lamv [c] < tauv [c] ∧ lamDev [c] > tauv [c] 8: wminv [c] ← ∞ if posv [c] = 0, else min πv [c], wminprvv [c] [c] where πv [c] = posv [c] if witv [c] and ∞ otherwise 9: wposv [c] ← wminprvv [c] [c] if posv [c] = 0, else wposparv [c]
10: deactv [c] ← witv [c] ∧ posv [c] = wposv [c] ▷ exactly one witness per cycle 11: end for 4:

Layer 12 (order: Br from the root, depth ≤ D) 12: deAbvv ← false if parv = ⊥ ∨ Recv = ̸ ∅; else if Recparv ̸= ∅ then deAbvv ←

∃c ∈

Recparv : deactparv [c] ; else deAbvv ← deAbvparv

Layer 13 (runs after deactivation: Layers 5–8 with isAP replaced by isAPv ∧ ¬deactv [c]) 13: compute lrun′v [c], rrun′v [c], run′v [c], pmax′v [c], Lam′v [c] by the rules of Algorithm 3 with that replacement

and that for fpos broadcasts the smallest such position, so exactly one of the at most two candidate runs is used.

4.4

Correctness and Complexity of Algorithm 1

We first show that the rules of Rule Sets 1–5 have a unique fixed point and that this fixed point is the canonical set S ∗ of Definition 19; the round and space bounds announced in Section 4.2 then follow. ▶ Theorem 37. The rules of Rule Sets 1–5 admit exactly one legitimate configuration, that is, exactly one configuration in which no process is enabled; its output is {v | inMVSv } = S ∗ , a maximum MVS of G containing no articulation point. Moreover, under the weakly fair distributed daemon every execution reaches that
configuration within O(D) rounds, and the algorithm is silent and uses O (γv + 1) log n bits per process after stabilization. Proof. Uniqueness of the legitimate configuration. In a configuration in which no process is enabled, every variable equals the value prescribed by its rule. The rule of Layer 1 pins distr = 0 and is the distance-plus-one rule elsewhere, whose only fixed point over the finite domain {0, . . . , N } is distv = dG (r, v) (Lemma 33), together with the tie-broken parent. Layers 2–15 satisfy the hypotheses of Lemma 31: the rule of a variable of layer i refers only to variables of layers j < i at v or at a neighbour of v, and to variables of layer i at

Y. Kim and Y. Sudo

XX:23

Algorithm 5 Rules for process v — Layers 14–15 (classification and output)

Layer 14 (order: C by increasing pos, then Br from the root) 1: for all c ∈ Recv do  2: fminv [c] ← ∞ if posv [c] = 0, else min φv [c], fminprvv [c] [c] where φv [c] = posv [c] if ¬isAPv ∧ lrunv [c] = 1 ∧ runv [c] = Lamv [c], and ∞ otherwise 3: fposv [c] ← fminprvv [c] [c] if posv [c] = 0, else fposparv [c] 4: if Lamv [c] > tauv [c] then 5: cyctypev [c] ← twin 6: else if Lamv [c] = tauv [c] then 7: cyctypev [c] ← unit 8: else if wposv [c] ̸= ∞ then 9: cyctypev [c] ← latent-twin 10: else 11: cyctypev [c] ← zero 12: end if 13: if cyctypev [c] ∈ {twin, latent-twin} then
14: selv [c] ← ¬isAPv ∧ run′v [c] = Lam′v [c] ∧ lrun′v [c] = 1 ∨ rrun′v [c] = 1 15: else if cyctypev [c] = unit then 16: selv [c] ← ¬isAPv ∧ runv [c] = Lamv [c] ∧ lrunv [c] = 1 ∧ posv [c] = fposv [c] 17: else 18: selv [c] ← false 19: end if 20: end for Layer 15 (local): output

21: inMVSv ← δ(v) = 1 ∧ ¬deAbvv ∨ ∃c ∈ Recv : selv [c]

in-neighbours of v in an acyclic evaluation order. By induction on the layer and, inside a layer, on the position in the evaluation order, the value of every variable in such a configuration is therefore uniquely determined by G. Hence there is exactly one legitimate configuration. The legitimate configuration has the intended values. We follow the layers. Throughout, C denotes a cycle component with non-tree edge eC = {a, b} and c = cid(C) = key(a, b). Layers 1–2 (BFS tree, cycle membership). Lemma 33 identifies the values of Layer 1, and Lemma 34 then gives {v | c ∈ Recv } = V (C), the identification of xC as the unique vertex of C with src[c] = 2, and the fact that no vertex outside V (C) holds c. In particular Recv is in bijection with the set of cycles through v, so |Recv | = γv . Layer 3 (geometry of C). Since xC = lca(a, b) and both a ⇝ xC and b ⇝ xC are tree paths, we have |C| = (dista − distxC ) + (distb − distxC ) + 1, which is the value assigned to size; hence tau = τC as well. Walking down the two tree paths from xC , the rule for pos enumerates V (C) as w0 = xC , w1 , . . . , w|C|−1 along C, the arm labelled 0 receiving the positions 1, 2, . . . and the arm labelled 1 the positions |C| − 1, |C| − 2, . . . ; consecutive positions are adjacent, the two positions on either side of eC being joined by eC itself. Consequently prvv [c] and nxtv [c] are well defined and are exactly the two neighbours of v on C. Note that |C| is obtained arithmetically from three BFS depths; at no point does a rule range over “all vertices carrying the same identifier”. Layer 4 (isAP computes A(G)). Let δ(v) ≥ 3. The cycles through v are edge-disjoint and each of them uses exactly two of the edges incident to v, so either some edge at v lies on no

XX:24

A Maximum Mutual Visibility Set on a Cactus Graph

cycle — and is then a bridge, whose removal together with v disconnects its other endpoint — or v lies on at least two cycles, which v separates. In both cases v ∈ A(G). Let δ(v) = 2. If v lies on a cycle C, then C − v is a path joining the two neighbours of v, and every other vertex reaches C without passing through v, so v ∈ / A(G); if v lies on no cycle, both its edges are bridges and v ∈ A(G). By Lemma 34 the condition “v lies on no cycle” is exactly Recv = ∅. Finally a leaf is never an articulation point, and the rule assigns false to it. These three cases are precisely the rule of Layer 4. Layers 5–8 (run and Lam = λC ). By Lemma 36 the vertex w0 = xC is an articulation point, so no ∅-free run of C contains w0 and every run is an interval of the path w1 , . . . , w|C|−1 . The recursions of Layers 5 and 6 are therefore grounded at w0 and are genuine path evaluations: an immediate induction gives that lrunv [c] (resp. rrunv [c]) is the number of vertices of the run containing v that lie between the beginning (resp. the end) of that run and v, inclusive. Hence runv [c] = lrunv [c] + rrunv [c] − 1 is the length of the run containing v, and it is 0 when v is a boundary vertex or v = w0 . Layer 7 accumulates the maximum of run along w1 , . . . , w|C|−1 , so pmaxw|C|−1 [c] = λC ; Layer 8 lets xC read that value from prvxC [c] = w|C|−1 and broadcasts it along Br , so Lamv [c] = λC for every v ∈ V (C). Layers 9–11 (beards, λvC , witnesses). The rule for chain is a leaf-to-root evaluation along Br whose fixed point is: chainv = true if and only if the subtree of Br rooted at v is a path whose vertices all have degree two in G and lie on no cycle, except its bottom vertex, which is a leaf of G. This is exactly (B1) and (B3) for the part of the graph below v. For a boundary vertex v of C, the branch Gv is a beard if and only if, in addition, v lies on exactly one cycle and carries exactly one edge outside that cycle, and Gv does not contain the root: these are the clauses |Recv | = 1, δ(v) = 3 and |TCv | = 1 with chainu , and the clause posv [c] ̸= 0 ∨ v = r, which excludes v = xC ̸= r, whose branch contains r and is therefore not a beard. Hence bBndv [c] is the predicate “v is a beard boundary vertex of C” of Definition 13. Since run vanishes on boundary vertices, alpha and beta are the lengths αv , βv of the two ∅-free runs adjacent to v, so lamDev [c] = max{λC , αv + 1 + βv } = λvC by the computation in the proof of Lemma 16, and witv [c] is the predicate “v is a witness of the latent twin-cycle C”. Finally wmin is a running minimum of the positions of the witnesses, wpos broadcasts the smallest of them, and deact marks exactly one witness per cycle. Layers 12–13 (deactivation). The rule for deAbv is a top-down evaluation along Br that propagates the deactivation flag of a boundary vertex to the vertices of the tree components ∗ hanging below it and stops at the next cycle; since the beard GvC∗ lies below vC in Br , its leaf zC is exactly the vertex with δ = 1 and deAbv = true. Layer 13 repeats Layers 5–8 with isAP replaced by isAP ∧ ¬deact, i.e., with the selected witness deactivated, so run′ and Lam′ are the run lengths and the maximum run length of the XC -free runs, where XC = ∅ ∗ for a twin-cycle and XC = {vC } for a latent twin-cycle. Layers 14–15 (classification and output). The four cases of the rule for cyctype are, in order, λC > τC , λC = τC , λC < τC with a witness, and λC < τC without one: this is verbatim Definition 13. For a twin- or latent twin-cycle the longest XC -free run is unique (Lemma 16) C and has length λX > τC ≥ 1, hence at least two vertices; its two endpoints are exactly C the vertices v of that run with lrun′v [c] = 1 or rrun′v [c] = 1, and they are not articulation ∗ points, again by Lemma 16. The conjunct ¬isAPv therefore excludes only the witness vC , which is internal to the run. For a unit-cycle, fmin marks the first vertex of each longest run and fpos broadcasts the smallest such position, so exactly one of the at most two candidate runs is used and exactly one vertex of it is selected. For a zero-cycle nothing is selected. Layer 15 finally sets inMVSv for every leaf whose beard was not deactivated and for every selected vertex of a cycle. Comparing with Definition 19, we conclude {v | inMVSv } = S ∗ ,

Y. Kim and Y. Sudo

with the two tie-breaks resolved by position instead of by index; since Lemmas 20 and 21 ∗ and Proposition 22 hold for every admissible choice of PC , uC and vC , this set is a maximum MVS by Theorem 26, and it contains no articulation point by Lemma 20. Convergence and silence. By Lemma 33 the variables of Layer 1 hold their prescribed values from the end of round D + 1 on, and the parent pointers one round later. Every one of the remaining 14 layers has depth O(D): the layers evaluated along Br have depth at most D, and the layers evaluated along a cycle C have depth at most |C| − 1 ≤ 2D, because a cycle component is an isometric subgraph of G (Observation 10) and hence ⌊|C|/2⌋ ≤ D. By Lemma 31 the system reaches the legitimate configuration within O(D) further rounds. Silence is immediate, a legitimate configuration being a fixed point of the rules. The space bounds are those established in the list of variables above and are restated in Proposition 39. ◀ ▶ Proposition 38. Algorithm 1 stabilizes in O(D) rounds under the distributed daemon. Proof. By Lemma 33, dist is correct after D + 1 rounds and par one round later, so Layer 1 is stable after D + 2 rounds. From that moment Lemma 31 applies to Layers 2–15. Their evaluation orders are either Br , of depth at most D, or a cycle C traversed by increasing or by decreasing position, of depth at most |C| − 1; and |C| ≤ 2D + 1 because a cycle component is an isometric subgraph of G (Observation 10). Each of the 14 layers therefore has depth O(D), and their number is a constant, so Lemma 31 yields a configuration in which every variable holds its prescribed value O(D) rounds later. By Theorem 37 that configuration is the unique legitimate one, and no process is enabled in it. The total is O(D) rounds. ◀
▶ Proposition 39. Algorithm 1 requires O (γv + 1) log n bits of memory per process v, where γv is the number of cycles in C(G) containing v. The total memory across all processes is O(n log n) bits, giving an average of O(log n) bits per process. Proof. We use the list of variables given in Section 4.3. The part of the state that does not depend on the cycles — parv , distv and the four booleans isAPv , chainv , deAbvv , inMVSv — occupies O(log n) bits, because parv is the identifier of a neighbour and distv ranges over {0, . . . , N } with N = nO(1) . Every field of a record is an identifier pair, a value of {0, . . . , N } ∪ {∞}, or a constant-size flag, and the number of fields is a constant, so a record occupies O(log n) bits. In an arbitrary configuration, v holds one record per element of Candv , and the rule for Candv in Rule Set 1 gives |Candv | ≤ |Evnt | + |ch(v)| ≤ δ(v); after stabilization
Recv consists exactly of the γv cycles through v by Lemma 34. Hence v uses O (δ(v)+1) log n
bits at all times and O (γv + 1) log n bits after stabilization. A cactus graph with k cycles P has exactly n − 1 + k edges and k ≤ (n − 1)/2, so v∈V δ(v) = 2|E| ≤ 3(n − 1) and X v∈V

γv =

X

|C| ≤ |E| = n + k − 1 = O(n).

C∈C(G)

P P Both bounds therefore give v∈V O (γv + 1) log n = O log n · (n + v γv ) = O(n log n) bits in total, that is, an average of O(log n) bits per process. ◀ ▶ Remark 40. Algorithm 1 is silent: once it has stabilized, no communication register changes. We deliberately do not claim that its average space is optimal. The Ω(log n) bound of Dolev, Gouda and Schneider [12] applies to silent algorithms whose registers allow a spanning structure of the network to be reconstructed, and a maximum MVS does not encode one, so the bound does not transfer to the problem studied here; it does apply to any algorithm following our strategy, whose registers encode Br , but that is a statement about the strategy

XX:25

XX:26

A Maximum Mutual Visibility Set on a Cactus Graph

and not about the problem. No non-trivial space lower bound is known for the maximum MVS problem, and establishing one is left open (Section 5). The worst case of Algorithm 1 also exceeds its average: a process on γv cycles stores Θ(γv log n) bits, and γv may be Θ(n) (e.g., at the centre of a friendship graph). ▶ Remark 41. Three design points deserve emphasis. First, identifying a cycle with its unique non-tree edge removes the circularity of naming a cycle after its minimum-depth vertex: the identifier is computable by the two endpoints of that edge alone, and the minimum-depth vertex is a conclusion of Layer 2 rather than a prerequisite for it. Second, |C| is obtained arithmetically from three BFS depths, so no rule ever ranges over all vertices carrying a given identifier; the remaining aggregations are running maxima and minima along the path w1 , . . . , w|C|−1 , which are ordinary layers. Third, all variables are recomputed by total assignments over finite domains, so a corrupted value is overwritten within one activation and a fabricated cycle identifier disappears as soon as its anchor is re-evaluated.

4.5

Algorithm 2: A Component-Local Self-Stabilizing Algorithm

Algorithm 2 replaces the single-root BFS of Algorithm 1 by a parallel multi-root BFS, at the cost of substantially increased memory. The key insight is that the decisions for a cycle component and its adjacent tree components can be taken as soon as the relevant local information has propagated within those components, without waiting for a global BFS tree to stabilize. Every process v with deg(v) ≥ 3 acts as a local root and constructs a BFS tree Bv rooted at itself, with tree identifier bfsid(v) = id(v); every process participates in all of them concurrently, keeping one BFS-distance entry per root in V δ3+ = {v ∈ V | deg(v) ≥ 3}. Phases 2–4 are then exactly those of Algorithm 1, with every propagation carried out inside the local trees Bv instead of a single global tree. Since every cycle component contains a vertex of V δ3+ — a boundary vertex of a cycle has degree at least three — cycle detection and the computation of λC , λvC inside a cycle component C complete in O(|C|) rounds. Crucially, Phase 4 is triggered independently for each component C as soon as Phases 2 and 3 have completed for C and its adjacent tree components, without waiting for the rest of the graph.

Instances, local roots and the rules of Algorithm 2 Concretely, Algorithm 2 runs one instance of the machinery of Section 4.3 for every ρ ∈ V δ3+ : in the instance of ρ the rules are those of Rule Sets 1–5 with the leader r replaced by ρ. Each instance is by itself an execution of Algorithm 1 with a different leader, so Theorem 37 applies to it verbatim; note that δ(ρ) ≥ 3 makes ρ an articulation point (see the proof of Theorem 37), so that Lemma 36 holds in every instance. The point of the replication is that a cycle component can be processed inside an instance whose root lies on it, and is then not delayed by the rest of the graph. Every cycle component C contains a vertex of V δ3+ : as G is connected and is not a simple cycle, C has a boundary vertex, and a boundary vertex of a cycle has degree at least three. We let ρC be the vertex of smallest identifier in V δ3+ ∩ V (C) and read the answer for C off the instance of ρC . Two points make this well defined and local. First, in the instance of a root ρ the minimum-depth vertex of C is ρ itself if and only if ρ ∈ V (C), that is, if and only if distxv [c] = 0 for the record of C in that instance; since distx is broadcast to all of V (C) in Layer 3, every vertex of C sees the same set V δ3+ ∩ V (C) of candidate roots and hence selects the same ρC . Second, a process must recognise, across instances, which records refer to the same cycle, and the identifier cid does depend on the instance, since which edge of C is a non-tree

Y. Kim and Y. Sudo

edge depends on the root. The matching is nevertheless local: in every instance the record of C at v determines the unordered pair {prvv [c], nxtv [c]} of the two neighbours of v on C (Layer 3), that pair does not depend on the instance, and two distinct cycles through v yield two disjoint pairs. Layers 12–15 are then evaluated in the selected instance only: the vertices of C, and the vertices of the tree components attached to C, use the values computed in the instance of ρC . Restricting the deactivation layers to one instance is what keeps the tie-break consistent — a latent twin-cycle may have several witnesses, and two instances may select different ones, so taking the disjunction of the deactivation flags over all instances could forfeit two leaves instead of one. The rule for deAbv is otherwise unchanged: it is run inside BρC , which is legitimate because ρC ∈ V (C), so every tree component attached to C lies below its boundary vertex in BρC .

Complexity analysis of Algorithm 2 ▶ Proposition 42. Algorithm 2 stabilizes in  
O max |C| + max |T | = O |Cmax | + |Tmax | C∈C(G)

T tree comp.

rounds under the distributed daemon. Proof. Write k = |Cmax | + |Tmax |, fix a cycle component C, and put ρ = ρC and U = V (C) ∪ S {V (T ) : T a tree component attached to C}. Since C is isometric in G (Observation 10) and ρ ∈ V (C), every u ∈ V (C) satisfies dG (ρ, u) ≤ ⌊|C|/2⌋, and every u in a tree component T attached to C satisfies dG (ρ, u) ≤ ⌊|C|/2⌋ + |T | ≤ k. By Lemma 33 applied to the instance of ρ, the variables dist of that instance are correct on the ball of radius k around ρ from the end of round k + 1 on, and the parent pointers one round later — and this holds however large the diameter of G is. From that moment Lemma 31 and Corollary 32 apply to the variables attached to the vertices of U in the instance of ρ. Each of the 14 layers propagates either along C, with depth at most |C| − 1, or inside a tree component attached to C, with depth at most |T |, or along the part of Bρ that joins the two, with depth at most k; and none of these evaluation orders leaves the ball of radius k around ρ, because C separates that ball from the rest of the graph at its boundary vertices. Every such variable therefore has dependency depth O(k), and Corollary 32 makes it stable after O(k) rounds. By Theorem 37 applied to the instance of ρ, the values reached are those prescribed by Definition 19; Layers 12–15 for U are evaluated in this instance and add O(k) further rounds. The argument applies to every cycle component simultaneously, and a leaf of a tree component attached to no cycle is selected unconditionally after O(1) rounds, so every process holds its final output after O(k) = O(|Cmax | + |Tmax |) rounds. ◀ The bound of Proposition 42 is genuinely component-local: it is not a restatement of the O(D) bound of Algorithm 1, and it cannot be improved as a function of |Cmax | and |Tmax |. Both points follow from the family described next, whose diameter is arbitrarily larger than |Cmax | + |Tmax |. ▶ Lemma 43. Let s ≥ 2, t ≥ 4, m ≥ 3, and let Γs,t,m be the cactus graph built as follows: a spine of m triangles joined consecutively by bridges; a cycle C of length c = 4s + 3 with exactly three boundary vertices p, v, q in this cyclic order, separated by runs of α = s + 1, β = s + 1 and γ = 2s − 2 non-articulation points; one endpoint of the spine attached to p by a bridge, a beard B of t vertices attached to v, and a star K1,3 attached to q. Write z for

XX:27

XX:28

A Maximum Mutual Visibility Set on a Cactus Graph

the leaf of B. Then |Cmax | = 4s + 3, |Tmax | = t and D = Θ(m + s + t), so |Cmax | + |Tmax | stays bounded while D grows without bound. Moreover C is a latent twin-cycle whose unique witness is v, and every maximum MVS of Γs,t,m containing no articulation point excludes z; if the star at q is deleted, then C becomes a twin-cycle and every such maximum MVS contains z. Proof. The parameters are immediate: τC = ⌊(c − 1)/2⌋ = 2s + 1 and λC = max{α, β, γ} = max{s + 1, 2s − 2} < 2s + 1 = τC , while λvC = α + 1 + β = 2s + 3 > τC ; the branches at p and at q are not beards (the first contains the spine, the second branches), so v is the only beard boundary vertex and hence the unique witness, and C is a latent twin-cycle. Deleting the star makes q a non-articulation point of degree two, which merges the runs β and γ into one of length β + 1 + γ = 3s > 2s + 1 = τC , so C becomes a twin-cycle. For the membership claims, recall from the proof of Theorem 26 that |S| is bounded by the sum of the local inequalities of Lemma 24, so a slack of δ in the term of a single cycle component yields |S| ≤ cap(G) − δ. Suppose z ∈ S; then v ∈ / IC and IC ⊆ {p, q}. If IC = ∅, then λICC = λC < τC , so |S ∩ V (C)| = 0 by Lemma 23(i) while cap(C) = 1: slack 1. If q ∈ IC , then cap∗ (C, q) = 3 (the three leaves of the star) while |S ∩ V (C)| ≤ 3 and cap(C) = 1: slack ≥ 1. If p ∈ IC , then cap∗ (C, p) ≥ m, because each triangle of the spine has two boundary vertices and hence λ = τ = 1, i.e., is a unit-cycle of capacity 1: slack ≥ m − 2 ≥ 0, and in fact slack ≥ 1 once m ≥ 3. In every case |S| ≤ cap(G) − 1 < µ(G), so z ∈ / S. Symmetrically, after deleting the star, suppose z ∈ / S; then v ∈ IC and cap∗ (C, v) = 1, while |S ∩ V (C)| ≤ 2 = cap(C) by Lemma 23(iii) when p ∈ / IC , and |S ∩ V (C)| ≤ 3 against cap(C) + cap∗ (C, v) + cap∗ (C, p) ≥ 2 + 1 + m when p ∈ IC : slack ≥ 1 in both cases, so z ∈ S. ◀ ▶ Proposition 44. Consider the task of computing a maximum MVS containing no articulation point—the task solved by both our algorithms, and without loss of generality by Lemma 7. Every correct self-stabilizing algorithm for this task needs Ω(s+t) = Ω(|Cmax |+|Tmax |) rounds on Γs,t,m . Since D = Θ(m + s + t) may be arbitrarily larger than |Cmax | + |Tmax | = Θ(s + t), the bound of Proposition 42 is asymptotically tight as a function of |Cmax | and |Tmax |, and is not implied by any bound in terms of the diameter. Proof. Let G′ be Γs,t,m with the star at q deleted. By Lemma 43, z outputs false in every legitimate configuration of Γs,t,m and true in every legitimate configuration of G′ , while the two graphs are isomorphic within distance r = t + s + 1 of z. Start the two executions from configurations agreeing on that common ball. Under the synchronous daemon—one of the schedules the distributed daemon may produce—the state of z after ρ ≤ r rounds depends only on the initial states within distance ρ, so z produces the same output in both, which is impossible once both have stabilized. Hence more than r = Ω(s + t) rounds are needed in one of them. ◀ ▶ Remark 45. Taking s, t constant—or simply a chain of m triangles with no attachments— gives cactus graphs with |Cmax | + |Tmax | = O(1) and D = Θ(n), on which Algorithm 2 stabilizes in O(1) rounds while Algorithm 1 needs Θ(D); this is the regime in which Algorithm 2 is worth its additional memory. Conversely, Ω(|Cmax | + |Tmax |) is not a lower bound on every cactus graph—if Tmax is a star attached to a cycle, its branching is visible at distance one—which is why Proposition 44 is stated for a family of instances. The second parameter must be |Tmax | and not the largest beard, since the leaf of a non-beard component must also learn that its component is not a beard.

Y. Kim and Y. Sudo

XX:29

Table 1 Complexity comparison of the two algorithms. Algorithm Algorithm 1 (single-root BFS) Algorithm 2 (component-local)

4.6

Stabilization time O(D) O(|Cmax | + |Tmax |)

Space per process O((γv + 1) log n) (average: O(log n)) O(|V δ3+ | log D + (γv + 1) log n)

Comparison of the Two Algorithms

▶ Proposition 46. Algorithm 2 requires O |V δ3+ | log D + (γv + 1) log n bits of memory per process v, where D is the diameter of G, |V δ3+ | is the number of vertices of degree at least three, and γv is the number of cycles containing v. Proof. The accounting is that of Proposition 39, with one BFS entry per root instead of one. Each process v maintains one distance entry distρv per root ρ ∈ V δ3+ ; each of them ranges over {0, . . . , N } but is only ever compared with distances of neighbours of v in the same instance, so O(log D) bits suffice once out-of-range values are clamped, contributing O(|V δ3+ | log D) bits in total, and the parent pointer of an instance is recovered from the distances of the neighbours. For each cycle C through v, the process keeps one record — the one of the instance of ρC — holding λC , τC , cid(C), the run and witness fields and the beard flag, each of O(log n) bits, hence O(γv log n) bits in total. The output variable inMVSv
occupies O(1) bits. Altogether a process uses O |V δ3+ | log D + (γv + 1) log n bits. ◀ ▶ Remark 47. The memory usage of Algorithm 2 is dominated by the O(|V δ3+ | log D) term, which can be significantly larger than the O(γv log n) per-process cost of Algorithm 1 when the number of high-degree vertices is large. In contrast, on cactus graphs where |V δ3+ | is small and where the largest cycle component and the largest tree component are much smaller than the diameter—i.e., |Cmax | + |Tmax | = o(D) —Algorithm 2 achieves both a strictly better stabilization time and a manageable memory footprint, making it preferable to Algorithm 1 in latency-sensitive applications. Table 1 summarizes the complexity of both algorithms.

5

Conclusion and Open Problems

We determined the mutual visibility number of cactus graphs, µ(G) = 2n2 + nlt + n1 + ℓ(G), via a cycle–tree decomposition and the classification of each cycle component as a zero-, unit-, twin- or latent twin-cycle, and we proposed two self-stabilizing algorithms that construct a maximum MVS under the distributed daemon: Algorithm 1 stabilizes in O(D) rounds with O(log n) average space per process, and Algorithm 2 in O(|Cmax | + |Tmax |) rounds—a bound that is asymptotically tight as a function of these two parameters even when they are o(D) (Proposition 44)—at the cost of increased memory. Three open problems suggest themselves. First, the MVN remains unresolved for classes that generalize cactus graphs—outerplanar graphs, series-parallel graphs, and graphs of bounded treewidth—all of which admit structured decompositions that may be amenable to the analysis developed here. Second, no non-trivial space lower bound is known for the maximum MVS problem: as explained in Remark 40, the Ω(log n) bound for silent stabilization [12] does not apply, because a maximum MVS does not encode a spanning structure of the network. Proving such a bound, and determining whether the worst-case per-process space O((γv + 1) log n) of Algorithm 1 can be reduced to O(log n), both remain open.

XX:30

A Maximum Mutual Visibility Set on a Cactus Graph

References 1 2

3 4

5

6

7 8 9

10 11 12 13 14 15 16

17 18 19

20

21

Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit. Introduction to Distributed Self-Stabilizing Algorithms. Morgan & Claypool Publishers, 2019. Davide Bilò, Alessia Di Fonso, Gabriele Di Stefano, and Stefano Leucci. On the approximability of graph visibility problems. In Proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), Lecture Notes in Computer Science. Springer, 2025. arXiv:2407.00409. Boštjan Brešar and Ismael G. Yero. Lower (total) mutual visibility in graphs. Applied Mathematics and Computation, 465:128411, 2024. Serafino Cicerone and Gabriele Di Stefano. Mutual-visibility in distance-hereditary graphs: A linear-time algorithm. In Proceedings of LAGOS 2023, volume 223 of Procedia Computer Science, pages 104–111, 2023. Serafino Cicerone, Gabriele Di Stefano, Luka Drožďek, Jaka Hedžet, Sandi Klavžar, and Ismael G. Yero. Variety of mutual-visibility problems in graphs. Theoretical Computer Science, 974:114096, 2023. Serafino Cicerone, Gabriele Di Stefano, and Sandi Klavžar. On the mutual-visibility in Cartesian products and in triangle-free graphs. Applied Mathematics and Computation, 438:127619, 2023. Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, and Ismael G. Yero. Mutual-visibility in strong products of graphs via total mutual-visibility. arXiv:2210.07835, 2022. Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, and Ismael G. Yero. Mutual-visibility problems on graphs of diameter two. European Journal of Combinatorics, 120:103995, 2024. Alain Cournier, Ajoy K. Datta, Franck Petit, and Vincent Villain. Snap-stabilizing PIF algorithm in arbitrary networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS), pages 199–206, 2002. Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643–644, 1974. Shlomi Dolev. Self-Stabilization. MIT Press, 2000. Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider. Memory requirements for silent stabilization. Acta Informatica, 36(6):447–462, 1999. Shlomi Dolev and Ted Herman. Superstabilizing protocols for dynamic distributed systems. Chicago Journal of Theoretical Computer Science, 1997. Shlomi Dolev, Amos Israeli, and Shlomi Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7(1):3–16, 1993. Swan Dubois, Toshimitsu Masuzawa, and Sébastien Tixeuil. The impact of topology on Byzantine containment in stabilization. In Proceedings of DISC 2010, 2010. Stephen T. Hedetniemi, David P. Jacobs, and Pradip K. Srimani. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. Journal of Parallel and Distributed Computing, 70(4):406–415, 2010. Shing-Tsaan Huang and Nian-Shing Chen. A self-stabilizing algorithm for constructing breadth-first trees. Information Processing Letters, 41(2):109–117, 1992. Damjan Korže and Aleksander Vesel. Variety of mutual-visibility problems in hypercubes. Applied Mathematics and Computation, 491:129218, 2025. Danilo Korže and Aleksander Vesel. Mutual-visibility and general position sets in Sierpiński triangle graphs. Discussiones Mathematicae Graph Theory, 44:1277–1291, 2024. doi:10.7151/ dmgt.2496. Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392–418, 2017. Gabriele Di Stefano. Mutual visibility in graphs. Applied Mathematics and Computation, 419:126850, 2022.