Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

Question

This question is about section 2.3 of Wilf's ``Algorithms and Complexity''

https://www.math.upenn.edu/~wilf/AlgoComp.pdf

in which he analyses the complexity of a recursive computation of the chromatic polynomial of a graph, based on the relation \begin{equation} \label{eq: recurrence} P(K;G)=P(K;G-\{e\})-P(K;G/\{e\}) \qquad (1). \end{equation} Here $P(K;G)$ is the number of ``proper colourings'' of $G$ with (as I understand it) at most $K$ colours (that is, colourings of the vertices using at most $K$ colours, such that no adjacent pair of vertices shares the same colour). The graph $G-\{e\}$ is the result of deleting edge $e$ from graph $G$, and the graph $G/\{e\}$ is the result of contracting edge $e$ in graph $G$. It turns out that $P(K;G)$ is indeed a polynomial in $K$, of degree equal to the number of vertices of $G$.

By defining $F(V,E)$ as the maximum cost (over all such graphs) of applying to a graph $G$ with at most $V$ vertices and at most $E$ edges, this recursive algorithm to compute $P(K;G)$, Wilf deduces from (1) that \begin{equation} \label{eq: F recurrence} F(V,E) \leq F(V,E-1)+cE+F(V-1,E-1) \qquad (2), \end{equation} with $F(V,0)=0$. Here the term $cE$ accounts for the effort of contracting the edge $e$, which requires us to modify the descriptions of any edges adjacent to the vertex that gets deleted.

Wilf seeks an upper bound of the form $F(V,E)\leq f(E)c$, and notes that the unique $f$ satisfying $f(E)=2f(E-1)+E$ and $f(0)=0$ will provide such a bound. He computes the exact solution $f$ of this last recurrence relation, which solution he approximates by $f(E)\sim2^{E+1}$.

He then derives another upper bound on $F$, by defining $\gamma(G)=|V(G)|+|E(G)|$, the sum of the number of vertices and the number of edges of $G$, and observing that $\gamma(G-\{e\})=\gamma(G)-1$ and $\gamma(G/\{e\})\leq \gamma(G)-2$. Then, letting $h(\gamma)$ denote the maximum amount of work done by the algorithm on any graph $G$ for which $\gamma(G)\leq \gamma$, Wilf claims that \begin{equation} \label{eq: h recurrence} h(\gamma)\leq h(\gamma-1)+h(\gamma-2) \qquad (3) \end{equation} for $\gamma \geq 2$. With $h(0)=h(1)=1$, the solution of this last recurrent inequality is that $h(\gamma) \leq F_{\gamma}$, the Fibonacci number.

Finally, combining the two bounds, he obtains that the time complexity of the algorithm is \begin{equation} O \left ( \min(2^{|E(G)|}, \phi^{|V(G)|+|E(G)|}) \right ), \end{equation} where $\phi$ is the golden ratio. Provided the ratio of $|E(G)|$ to $|V(G)|$ is large enough, the second bound is sharper than the first.

My question is, how in (3) was Wilf able to omit a term like $cE$ from (2) ?

Answer 1

You are correct that a term was omitted in the RHS of (2.3.10), but the final asymptotic bound $O(\phi^n)$ holds for the augmented RHS also. Perhaps it might be easier for you to see this if you just work out the solution for the nonhomogeneous recurrence relation from scratch rather than use Wilf's Theorem 1.4.1 on the epsilons, as shown below. Essentially, we are adding a linear term $an+b$ to the exponential $\phi^n$, which gives $\phi^n + an+b = O(\phi^n)$, where $\phi$ is the golden ratio.

More specifically, suppose that before the two recursive function calls to the chrompoly function, the edge set needs to be modified, and for the given value of $\gamma = |V|+|E|$, the cost for modifying the edge set is $\gamma$. (You can also take this cost to be $c \gamma$ for some other $c$, if you wish.)

Then, the recurrence $h(n) = h(n-1)+h(n-2)+n$ needs to be solved. From the theory of linear nonhomogeneous recurrence relations, the solution $h(n)$ is the sum of a generation solution and a particular solution, where (1) the general solution has the form $h_1(n) = c_1 \alpha^n + c_2 \beta^n$, where $\alpha , \beta$ are roots of the characteristic equation (one of them containing the golden ratio), and (2) the particular solution has the form $h_2(n) = an+b$ because the nonhomogeneous part is polynomial of degree $1$. (If the nonhomogeneous part was $7n^2 3^n$, then the particular solution would take the form $(an^2+bn+c)3^n$. If $3$ was a single root of the characteristic equation, then the particular solution would take the form $n(an^2+bn+c)3^n$. If $3$ appeared as a root with multiplicity $m$, then the extra factor would be $n^m$.)

Thus, $h(n) = O(c \phi^n +an+b) = O(\phi^n)$ because the linear terms grow more slowly than the exponential and can be ignored in asymptotic notation.