In computer science, a Minimum Spanning Tree (MST) connects all nodes in a weighted graph using the cheapest possible edges without creating any cycles.

All CS Students will recognize these two greedy algorithms:

• Kruskal’s Algorithm: Sorts all the edges from smallest to largest weight and adds them one by one as long as they dont form cycles.
• Prim’s Algorithm: Starts at one node and builds the tree outward by picking the cheapest connected edge at each step.

What we are testing with Statistics:

1. Hypothesis Testing & \(p\)-values: Does Prim’s actually run faster than Kruskal’s on dense graphs (graphs with lots of edges), or is the speed difference not significant?
2. Simple Linear Regression: Can we use the number of edges in a graph to predict how long each algorithm takes to run?

For a graph with \(n\) nodes, the maximum possible number of edges is \(\frac{n(n - 1)}{2}\). We define Graph Density (\(D\)) as the proportion of possible edges that actually exist in the graph:

\[D = \frac{2m}{n(n - 1)}\]

To test if the average runtime (\(\mu\)) of Kruskal’s and Prim’s is different on dense graphs (\(D \ge 0.7\)), we set up our null and alternative hypotheses using a significance level of \(\alpha = 0.05\):

\[H_0: \mu_{\text{Kruskal}} = \mu_{\text{Prim}}\]

\[H_a: \mu_{\text{Kruskal}} \neq \mu_{\text{Prim}}\]

We calculate our test statistic using a two-sample \(t\)-test:

\[t = \frac{\bar{x}_1 - \bar{x}_2}{\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}}\]

Here is the R code used to simulate 120 random graphs (with 150 nodes each) and run the \(t\)-test on the dense graphs:

num_nodes <- 150
max_edges <- num_nodes * (num_nodes - 1) / 2
density <- runif(120, min = 0.10, max = 0.95)
edges <- round(density * max_edges)

kruskal_time <- 0.0016 * (edges * log2(edges)) + rnorm(120, mean = 2, sd = 3.5)
prim_time <- 0.0045 * (num_nodes^2 + edges) + rnorm(120, mean = 2, sd = 3.0)

mst_data <- data.frame(
  Edges = rep(edges, 2),
  Density = rep(density, 2),
  Time_ms = c(kruskal_time, prim_time),
  Algorithm = rep(c("Kruskal", "Prim"), each = 120)
)

dense_data <- subset(mst_data, Density >= 0.7)
t.test(Time_ms ~ Algorithm, data = dense_data)$p.value

## [1] 1.282849e-18

When we take a look at these boxplots what we can see is that Kruskals performs best when there are low edge counts, but the moment theres more edges it begins to really slow down because it has to sort all of them and Prim’s pulls ahead by a lot.

Next, we use Simple Linear Regression to predict the runtime (\(y\)) based on the number of edges (\(x\)):

\[\hat{y} = b_0 + b_1 x\]

Where \(b_1\) is the slope and \(b_0\) is the y-intercept, calculated from our sample data as:

\[b_1 = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2}, \quad b_0 = \bar{y} - b_1 \bar{x}\]

To check how well the regression line fits our data, we use the \(R^2\) value (proportion of variance explained):

\[R^2 = 1 - \frac{\text{SSE}}{\text{SST}} = 1 - \frac{\sum (y_i - \hat{y}_i)^2}{\sum (y_i - \bar{y})^2}\]

To see what the algorithms are actually building, here is a 3D plot of 25 random points connected by their Minimum Spanning Tree:

• Hypothesis Test Conclusion: Since our \(p\)-value (\(1.99 \times 10^{-36}\)) is way below \(\alpha = 0.05\), we reject \(H_0\). Prim’s is significantly faster on dense graphs.
• Regression Takeaway: The number of edges has a strong linear relationship with runtime. Kruskal’s has a much steeper slope (\(b_1\)) than Prim’s, crossing over around 6,000 edges.