# Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in:

$$T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + c_2 (n-i)i + c_3 n & \text{otherwise} \end{cases}$$

The restrictions on $$i$$ and $$j$$ are as follows: $$0 < i < n$$ $$0 \leq j \leq m$$ $$0 < m - i - j \leq m$$

The problem this algorithm solves is as follows:

Given a graph $$G$$ and a spanning tree of $$G$$, $$T$$. You are told $$T$$ is an "almost"-MST of $$G$$. An "almost"-MST is defined as a spanning tree of $$G$$, for which the removal and replacement of one edge in $$T$$ with another edge in $$G \setminus T$$, we can achieve a minimum spanning tree. Determine the edge to be removed from $$T$$ and the edge to be replaced in $$G \setminus T$$.

Note: I know there are $$O(n + m)$$ algorithms to solve this. I am curious about the complexity of my algorithm however.

More background: My algorithm attempts to solve this as a variant of the Tree Path Maxima Problem. For any edge $$(u,v)$$ not in our spanning tree $$T$$, we can check $$w(u,v)$$ against the path maxima from $$u$$ to $$v$$ in $$T$$. If the path maxima if greater than $$w(u,v)$$ we can swap these two edges and get a lesser weight MST.

Assume we are given the input as $$G = (V, E)$$, $$T = (V, E')$$, and $$E^* = G.E \setminus T.E$$. Assume we also have an empty table (function) $$\gamma$$ of uninitialized data. The general idea of the algorithm is as follows:

1. If $$T.V$$ has less than or equal to two nodes or $$E^*$$ is empty, return null.
2. Let $$e$$ be the maximum weight edge in $$T$$.
3. Cut $$T$$ on $$e$$, into $$T_1$$ of $$n-i$$ nodes and $$T_2$$ and $$i$$ nodes.
4. Let $$E^*_1$$ and $$E^*_2$$ be empty edge sets.
5. If $$|T_1.V| \times |T_2.V| < |E^*|$$:
1. For all edges $$(u,v)$$ where $$u \in T_1$$ and $$v \in T_2$$, store $$\gamma(u,v) = e$$.
2. Set $$E^*_1 = E^*_2 = E^*$$ where $$|E^*| = m$$.
6. Else:
1. For all edges $$(u,v) \in E^*$$:
• If $$u \in T_1$$ and $$v \in T_2$$:
• If $$w(u,v) < w(e)$$, return $$((u,v), e)$$.
• Else If $$u \in T_1$$:
• Add $$(u,v)$$ to $$E^*_1$$.
• Else:
• Add $$(u,v)$$ to $$E^*_2$$.
2. At this point we have $$|E^*_1| = m - j - k$$ and $$|E^*_2| = k$$.
7. Recurse on $$\{G, T_1, E^*_1\}$$.
8. Recurse on $$\{G, T_2, E^*_2\}$$.
9. If (7) and (8) return null, then return null, else return (7) or (8) resp.

If the initial call returns null, then do the following:

• For all $$(u,v) \in E^*$$:
• If $$\gamma(u,v) \neq$$ null and $$w(u,v) < w(\gamma(u,v))$$:
• Return $$((u,v), \gamma(u,v))$$

All of this takes advantage of the following lemma:

For all edges $$(u,v) \in G$$, if $$w(u,v) < w(\gamma_T(u,v))$$ then $$T$$ is not a minimum spanning tree in $$G$$. Where $$\gamma_T(u,v)$$ is the maximum weight edge on the path from $$u$$ to $$v$$ in a spanning tree $$T$$ of $$G$$.

I am not too concerned about the algorithm itself (though if you have comments, I am receptive). I am mostly wondering about the best approach to do worst-case analysis on this recurrence in terms of $$n$$ and $$m$$ (the size of the original graph).

1. Is this the correct formulation of the recurrence in the algorithm?
2. What is the best way to do worst-case analysis on this algorithm?

The issue I am currently having with analysis is that $$m$$ and $$j$$ are correlated. For example, when $$G$$ is dense, we have $$m \approx n^2$$. Thus, when removing the $$j$$ edges between $$T_1.V$$ and $$T_2.V$$ we will remove somewhere between $$\Theta(n)$$ and $$\Theta(n^2)$$ edges. You can see how this could change the runtime drastically.

• You can guess the solution by comparing the two extreme cases $i=k=1$ and $i=n/2$, $k=m/2$ (this is ignoring $j$). You can solve these recurrences explicitly. Pick the worse solution, and try to prove inductively that it is an upper bound in the general case as well. – Yuval Filmus Mar 30 at 20:48
• I thought about that. Is that "sandwich-ing" formal? I guess by your last sentence, a proof by induction would show that. I will try that and update. – ryan Mar 30 at 20:54
• In attempting this analysis I realized my constraints were incorrect. We have guarantees, if $m$ is large, then $j$ will have to be somewhat large. In step (2) where I remove $j$ edges, these are all edges that connect $G_1$ and $G_2$. If $G$ is dense, then $m$ and $j$ will be quite large respectively. If $G$ is sparse then $m$ and $j$ will both be quite small respectively. Ignoring $j$ this algorithm appears to be $O(m^2)$ worst case, but $j$ should prevent this from being greater than $O(n^2)$ worst case. – ryan Mar 30 at 21:08
• What's $k$? Is it a fixed constant? It shows up in your recurrence but the variable is never defined. I don't understand how you can write $T(n,m) =$ ... some expression of $i,j,n,m,k$ ... -- that doesn't make sense. The right-hand side should only depend on $n,m$. Do you perhaps mean $T(n,m) = \max \{... : 0<i<n, ...\}$, i.e., the right-hand side is a max over all $i,j,k$ in some range? I have a similar confusion of your algorithm. How is $j$ chosen in step 2 of your algorithm? Do you choose $j$, and then find $G_1,G_2$? – D.W. Apr 1 at 0:31
• @D.W. (1) All variables in $\{i, j, k, n, m\}$ are defined implicitly or explicitly in the description of the algorithm, where $n$ and $m$ are standard # of nodes in $G$ and # of edges in $G$ resp. (2) Yes, in the worst case $T(n,m)$ would be $\max\{\}$ over all possible (e.g. allowed by the constraints) values of $i$, $j$, and $k$. (3) I will update the algorithm description to explain how $j$ is determined. – ryan Apr 1 at 0:51