The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is a great book to start learning how to design exact exponential algorithms. In their second chapter, they present the recurrence relations in the framework of a branching algorithm:

$ T (n) leq T (n-t_1) + T (n-t_2) + points T (n-t_r) $

To solve this equation, we assume $ T (n) = c ^ n $, then $ c $ should be a (complex) root of $ x ^ n – x ^ {n-t_1} -x ^ {n-t_2} – dots-x ^ {n-t_r} = 0 $ -> the execution time of this branching algorithm is therefore governed by the largest (real) root of this equation. We call $ tau (t_1, t_2, dots, t_r) $ the branching factor of these $ t_r $ numbers which is therefore the largest positive real root of the corresponding equation. The branch vector is defined as $ t = (t_1, t_2, dots, t_r) $

I am mainly interested in editing such branching algorithms in order to reduce the operating time. Often, I find myself in a situation where I can either do:

(1) delete a branch entirely (i.e. reduce the number of arguments in the branching factor)

(2) have the choice between two branching vectors, say $ x $ and $ y $. Branching vectors are equal except for two elements: we have $ x_i <y_i $ and $ x_j> y_j $ with $ i neq j $. (($ x_i $ is therefore element in position $ i $ branching vector $ x $).

I have two questions:

(1) intuitively, it seems to me that if I delete a branch entirely, it decreases the execution time of the algorithm. We are basically trying to find the leaf count of the branching algorithm; by definition, if you delete an entire branch, the number of leaves should decrease, hence the execution time. However, I do not find any such theorem / proof in the literature.

Mathematically, you basically have an equation of the form $ sum a_i x ^ {n – c_i} = 0 $, where we only care about the biggest positive real root. Now if i create the same equation but now lower one of the $ a_i $ values, is my real positive root decreasing? I guess it's a fundamental / elementary theorem somewhere but doesn't seem to find it.

(2) The book has a lemma (2.3): $ tau (i, j) ge tau (i + epsilon, j – epsilon) $ for everyone $ 0 le i le j $ and all $ 0 le epsilon le frac {j-i} {2} $. I can't use this lemma in most cases of this problem. I'm going to assume that I will just have to calculate the roots for each branch, right? And then take the minimum? Or is there a more fundamental theorem for this?

META: should I (cross) post this on TCS?