The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they present the recurrence relationships in the context 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 $ must 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 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 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 to reduce runtime. Often, I find myself in a situation where I can do:

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

(2) you can choose between two branch vectors, let's say $ x $ Y $ and $. The branching vectors are the same except for two elements: we have $ x_i <y_i $ Y $ x_j> y_j $ with $ i neq j $. ($ x_i $ it is therefore an element in position $ i $ branching vector $ x $)

I have two questions:

(1) Intuitively, it seems to me that if I remove a branch entirely, this reduces the execution time of the algorithm. Basically we try to find the number of leaves of the branching algorithm; by definition, if we remove an entire branch, the number of sheets should decrease, therefore the execution time should be less. However, I cannot find such a theorem / proof in the literature.

Mathematically, you essentially have an equation of the form $ sum a_i x ^ {n – c_i} = 0 $, where we only care about the largest positive real root. Now I do create the same equation, but now one of the $ a_i $ values, does my positive real root decrease? I suppose this is a fundamental / elementary theorem somewhere, but I can't seem to find it.

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

GOAL: Should I (cross) post this on TCS?