betaFeedback

WorksMathematics

CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph

Abstract

The minimum spanning arborescence (MSA) with a fixed boundary, defined on weighted directed graphs, is the directed analogue of the minimum spanning tree (MST). The behaviour of the MSA has been of recent interest and is known to be quite different from that of its undirected counterpart. On the complete directed graph, and for edge weights given by i.i.d. random variables with a broad class of distributions, we prove a Central Limit Theorem for the weight of the MSA with appropriate scaling. While the scaling for the CLT is similar to MST case explored by Janson, the centering required (11 as opposed to ζ(3)ζ(3) for Uniform[0,1][0,1] weights) and the limiting variance of the Gaussian (11 as opposed to 6ζ(4)−4ζ(3)6ζ(4)-4ζ(3) for Uniform[0,1][0,1] weights) are notably different.

Introduction

Let G⃗=(V,E⃗)\vec{G}=(V,\vec{E}) be a graph where each edge comes with a specific direction and there are no self-loops. More precisely, E⃗\vec{E} is a subset of the following set of ordered pairs

{(u,v):u,v∈V, u≠v}\{(u,v):u,v\in V,\ u\ne v\}

If e⃗∈E⃗\vec{e}\in\vec{E}, such that e⃗=(u,v)\vec{e}=(u,v), we say that uu is the tail of e⃗\vec{e} and vv is the head of e⃗\vec{e} and denote them by e⃗−\vec{e}^{-} and e⃗+\vec{e}^{+}, respectively. We say e⃗\vec{e} is an outgoing edge from uu and an incoming edge to vv. A directed path is a sequence of distinct edges e⃗1,e⃗2,⋯ ,e⃗n\vec{e}_1,\vec{e}_2,\cdots,\vec{e}_n such that e⃗i+=e⃗(i+1)−\vec{e}_i^{+}=\vec{e}_{(i+1)}^{-}, for all 1≤i<n1\le i<n. If there is a directed path e⃗1,e⃗2,⋯ ,e⃗n\vec{e}_1,\vec{e}_2,\cdots,\vec{e}_n such that e⃗n+=e⃗1−\vec{e}_n^{+}=\vec{e}_1^{-}, we say that this path creates a directed cycle. Sometimes we denote a directed cycle by the set of heads and tails of the edges in it. If there is a directed path from a vertex uu to a vertex vv, we say that uu is in the past of vv, and denote it as u∈Past⁡vu\in\operatorname{Past}_v. Note that our definition admits paths. with no edges, so v∈Past⁡vv \in\operatorname{Past}_v, for all v∈Vv \in V.

The setting of this article is on the complete directed graph K⃗n=(Vn,E⃗n)\vec{K}_n = (V_n,\vec{E}_n), where VnV_n is a set of nn vertices, and E⃗n\vec{E}_n is the set of all possible directed edges. More precisely, the edge set of the complete directed graph is given by

E⃗n={e⃗=(u,v):u,v∈Vn, u≠v}.\vec{E}_n = \{\vec{e} = (u,v) : u,v \in V_n,\ u \ne v\}.

See Figure 1 for an example.

The complete directed graph on 5 vertices with distinguished vertex ∂

Figure 1. The complete directed graph on 5 vertices with distinguished vertex ∂\partial.

Definition 1.1. An arborescence, denoted (T⃗,∂)(\vec{T},\partial) is a finite directed graph T⃗=(V(T⃗),E(T⃗))\vec{T} = (V(\vec{T}),E(\vec{T})) with boundary ∂∈V(T⃗)\partial\in V(\vec{T}), which has the following properties:

  1. ∂\partial has no outgoing edge,

  2. all vertices v∈V(T⃗)∖{∂}v \in V(\vec{T}) \setminus\{\partial\} have exactly one outgoing edge,

  3. there are no directed cycles and

  4. the graph is connected in the undirected sense.

Definition 1.2. A spanning arborescence (T⃗,∂)(\vec{T},\partial) of a finite directed graph (G⃗,∂)(\vec{G},\partial), where ∂\partial is a distinguished vertex, is an arborescence with boundary ∂\partial such that V(T⃗)=V(G⃗)V(\vec{T}) = V(\vec{G}) and E(T⃗)⊂E(G⃗)E(\vec{T}) \subset E(\vec{G}).

See Figure 2 for an example.

A spanning arborescence of the complete directed graph on 5 vertices

Figure 2. The red edges form a spanning arborescence of (K⃗5,∂)(\vec{K}_5,\partial).

Remark 1.3. For a spanning arborescence, given conditions 1 and 2 in Definition 1.1, points 3 and 4 are equivalent to saying that the underlying undirected graph is a spanning tree, and then all edges are directed towards ∂\partial.

Remark 1.4. In an arborescence, from each vertex there is a unique directed path to ∂\partial.

The article concerns the behaviour of the spanning arborescence of (K⃗n,∂)(\vec{K}_n,\partial) that has minimum weight when the edges are assigned random weights. This means that each of the directed edges of K⃗n\vec{K}_n is assigned an independent non-negative random variable with density p(x)p(x), which satisfies the following properties:

  • p(0)>0p(0)>0,

  • pp is continuous at 00,

  • ∫0∞xp(x) dx<∞\int_0^\infty xp(x)\,\mathrm{d}x<\infty.

We denote this family of random variables by {Ye⃗}e⃗∈E⃗n\{Y_{\vec e}\}_{\vec e\in\vec E_n} and define the weight of a spanning arborescence (T⃗,∂)(\vec T,\partial) of (K⃗n,∂)(\vec K_n,\partial) to be

W(T⃗)=∑e⃗∈E⃗(T⃗)Ye⃗.W(\vec T)=\sum_{\vec e\in\vec E(\vec T)}Y_{\vec e}.

The minimum spanning arborescence (MSA) on (K⃗n,∂)(\vec K_n,\partial) is then defined to be

(T⃗n∗,∂):=arg min⁡{W(T⃗):(T⃗,∂) is a spanning arborescence on (K⃗n,∂)}.(\vec T_n^*,\partial):=\operatorname*{arg\,min}\{W(\vec T):(\vec T,\partial)\text{ is a spanning arborescence on }(\vec K_n,\partial)\}.

We will denote by Wn∗W_n^* the weight of the minimum spanning arborescence. Note that the minimum spanning arborescence is almost surely unique as the weights on the edges are continuous random variables. The main result of this article is the following:

Theorem 1.5. Let i.i.d. weights {Ye⃗}e⃗∈E⃗n\{Y_{\vec e}\}_{\vec e\in\vec E_n} be assigned to the edges of (K⃗n,∂)(\vec K_n,\partial) whose common density pp satisfies the previous hypotheses. Let Xv(n):=min⁡e⃗−=vYe⃗X_v^{(n)}:=\min_{\vec e_-=v}Y_{\vec e}. Then as n→∞n\to\infty,

n(Wn∗−nE(Xv(n)))→dN(0,1p(0)2).\sqrt{n}\left(W_n^*-n\mathbb{E}\left(X_v^{(n)}\right)\right)\xrightarrow{d}\mathcal{N}\left(0,\frac{1}{p(0)^2}\right).

Since {Ye⃗}e⃗∈E⃗n\{Y_{\vec e}\}_{\vec e\in\vec E_n} are i.i.d., {Xv(n)}v∈Vn∖{∂}\{X_v^{(n)}\}_{v\in V_n\setminus\{\partial\}} are also i.i.d. For brevity we remove the suffix and denote them as X(n)X^{(n)}, for all v∈Vn∖{∂}v\in V_n\setminus\{\partial\}. The limiting variance is 1p(0)2\frac{1}{p(0)^2} since lim⁡n→∞n2Var⁡(X(n))=1p(0)2\lim_{n\to\infty}n^2\operatorname{Var}\left(X^{(n)}\right)=\frac{1}{p(0)^2}, we can derive it as an immediate corollary of Lemma 6.1.

References

  1. [2]F. Bock. “An algorithm to construct a minimum directed spanning tree in a directed network”. In: Developments in Operations Research (1971). Gordon and Breach, New York, pp. 29–44.
  2. [4]Sky Cao. “Central limit theorems for combinatorial optimization problems on sparse Erdős–Rényi graphs”. In: Ann. Appl. Probab. 31.4 (2021), pp. 1687–1723. ISSN: 1050-5164,2168-8737. DOI: 10.1214/20-aap1630. URL: https://doi.org/10.1214/20-aap1630.
  3. [5]Partha S. Dey and Grigory Terlov. “Random optimization problems at fixed temperatures”. In: Transactions of the American Mathematical Society (2024). URL: https://api.semanticscholar.org/CorpusID:267627204.arxiv.org/abs/2402.07825
  4. [6]Jack Edmonds. “Optimum branchings”. In: J. Res. Nat. Bur. Standards Sect. B 71B (1967), pp. 233–240. ISSN: 0022-4340.DOI
  5. [7]William Feller. “The Fundamental Limit Theorems in Probability”. In: Bulletin of the American Mathematical Society 51.11 (1945), pp. 800–832. DOI: 10.1090/S0002-9904-1945-08448-1.DOI
  6. [8]Alan M. Frieze. “On the Value of a Random Minimum Spanning Tree Problem”. In: Discrete Applied Mathematics 10.1 (1985), pp. 47–56. DOI: 10.1016/0166-218X(85)90058-7.DOI
  7. [9]Alan M. Frieze and Tomasz Tkocz. “A Randomly Weighted Minimum Arborescence with a Random Cost Constraint”. In: Mathematics of Operations Research 47.2 (2022), pp. 1664–1680. DOI: 10.1287/moor.2021.1184.DOI
  8. [10]Jennie C Hansen. “Limit laws for the optimal directed tree with random costs”. In: Combinatorics, Probability and Computing 6.3 (1997), pp. 315–335.DOI
  9. [11]Svante Janson. “The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph”. In: Random Structures & Algorithms 7.4 (1995), pp. 337–355.DOI
  10. [13]Johan Wästlund. Evaluation of Janson’s Constant for the Variance in the Random Minimum Spanning Tree Problem. Linköping Studies in Mathematics 7. Linköping, Sweden: Linköping University Electronic Press, 2005. URL: https://www.diva-portal.org/smash/record.jsf?pid=diva2:375259.

Paper details

vlnc:W_ytsraraj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents