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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 30 at 20:48
  • $\begingroup$ 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. $\endgroup$ – ryan Mar 30 at 20:54
  • $\begingroup$ 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. $\endgroup$ – ryan Mar 30 at 21:08
  • $\begingroup$ 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$? $\endgroup$ – D.W. Apr 1 at 0:31
  • $\begingroup$ @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. $\endgroup$ – ryan Apr 1 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.