2
$\begingroup$

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) ?

$\endgroup$
10
  • 1
    $\begingroup$ After stating the recurrence (2.3.10) on page 46, Wilf explains why it holds. Are you not convinced by the explanation? $\endgroup$ May 24, 2019 at 7:24
  • 2
    $\begingroup$ In addition, Theorem 1.4.1 guarantees that this additional summand wouldn't make any difference asymptotically. $\endgroup$ May 24, 2019 at 7:25
  • 1
    $\begingroup$ I don't really understand your point about $+\epsilon$ in the exponent. It only affects the answer by a constant factor, which big O notation is completely oblivious to. $\endgroup$ May 27, 2019 at 11:09
  • 1
    $\begingroup$ Regarding the right-hand side of 2.3.10, I haven't examined it closely, but there could definitely be a mistake. $\endgroup$ May 27, 2019 at 11:10
  • 1
    $\begingroup$ Wilf might have made a mistake, or perhaps the recurrence holds for a subtle reason. However, he does provide some explanation. If you don't find his explanation convincing, then it's probably a mistake. Books and lecture notes are full of them. The right attitude is to take this into account when reading. If some argument is incorrect, you can try to fix it. $\endgroup$ May 27, 2019 at 20:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much, and many apologies for being so slow to respond to your nice answer. I have been really busy. $\endgroup$
    – Simon
    Jul 25, 2019 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.