Fix false negative in minimum and maximum spanning arborescence (fixes #8964) - #8979

I don't think I understand this. Is it checking for the case of no edges? If so, how can we be looking for a maximum branching?

When G has no edges, min_weight is INF and max_weight is -INF, which causes the subsequent weight arithmetic (max_weight - min_weight) to produce NaN and crash.

For an edgeless graph, the only branching is the empty graph (0 edges), which is trivially both minimal and maximal. Calling maximum_branching(G, ...) was just a convenient way to get an empty graph of the appropriate type/nodes/attrs.

If preferred, I can change this to directly return G.copy() (or type(G)() with nodes added) to make it clearer that it's just returning an empty branching.

I'd prefer returning G.copy(). Otherwise each time I read this part of the code I will need to go look up what maximum_branching does with an empty_graph. :}
Thanks!

Can you explain why this formula works?
Where do these values come from in terms of a spanning and a non-spanning branching?

In minimal_branching, we transform weights as $w'(e) = S - w(e)$ and run maximum_branching.

For any branching $B$, its transformed weight is:
$\sum_{e \in B} w'(e) = |B| \cdot S - \sum_{e \in B} w(e)$

A spanning arborescence $T$ has exactly $n - 1$ edges, while any non-spanning branching $B$ has $|B| \le n - 2$ edges. For $T$ to be preferred over $B$ by maximum_branching, we need $w'(T) > w'(B)$:
$((n - 1) - |B|) \cdot S > w(T) - w(B)$

Since $(n - 1) - |B| \ge 1$, this holds if $S > w(T) - w(B)$.

To bound the maximum possible gap $w(T) - w(B)$:

• In the worst case, $w(T)$ could sum $n - 1$ edges of weight $\max(w_{\max}, 0)$.
• $w(B)$ could sum at most $n - 2$ edges of weight $\min(w_{\min}, 0)$ (if negative).

So the gap is at most $(n - 1) \cdot \max(w_{\max}, 0) - (n - 2) \cdot \min(w_{\min}, 0)$. Setting $S$ greater than this guarantees that every spanning arborescence beats every non-spanning branching. (The extra max_weight + 1 + (max_weight - min_weight) term keeps the legacy shift so transformed weights also stay positive).

Alternatively, an even simpler upper bound on $w(T) - w(B)$ is $2 \sum |w| + 1$ if you prefer that over tracking $n$.

Thanks for this description! Very helpful.

In the end, I think the simpler (though probably bigger than needed) upper bound is a better choice -- easier to read anyway... Is it also faster to compute? Would it be even better to use
2 * n * (max_weight - min_weight) + 1 (and do we need to max when negative and min when positive? We can be very generous with our upper bound estimate so long as it gets bigger... any way to help that simplify the expression and logic here? )

Can you explain why this formula is correct?

Same reasoning as in minimal_branching, but in reverse: here we shift weights $w'(e) = w(e) + S$ and run maximum_branching.

For a spanning arborescence $T$ ($n - 1$ edges) and a non-spanning branching $B$ ($\le n - 2$ edges):
$w'(T) > w'(B) \iff ((n - 1) - |B|) \cdot S > w(B) - w(T)$

Since $(n - 1) - |B| \ge 1$, we need $S > w(B) - w(T)$.

The worst-case advantage $B$ could have over $T$ in raw weights is:

• $B$ has at most $n - 2$ edges, each at most $\max(w_{\max}, 0)$.
• $T$ has $n - 1$ edges, each at least $\min(w_{\min}, 0)$ (which can be negative).

So $w(B) - w(T) \le (n - 2) \cdot \max(w_{\max}, 0) - (n - 1) \cdot \min(w_{\min}, 0)$.

Setting $S$ above that ensures maximum_branching never drops an edge needed to span the graph. The first term 1 - min_weight + (max_weight - min_weight) is the existing legacy shift to ensure positivity during Edmonds' contraction.