  We prove lower bounds on pure dynamic programming algorithms for maximum
weight independent set (MWIS). We model such algorithms as tropical circuits,
i.e., circuits that compute with $\max$ and $+$ operations. For a graph $G$, an
MWIS-circuit of $G$ is a tropical circuit whose inputs correspond to vertices
of $G$ and which computes the weight of a maximum weight independent set of $G$
for any assignment of weights to the inputs. We show that if $G$ has treewidth
$w$ and maximum degree $d$, then any MWIS-circuit of $G$ has $2^{\Omega(w/d)}$
gates and that if $G$ is planar then any MWIS-circuit of $G$ has
$2^{\Omega(w)}$ gates. An MWIS-formula is an MWIS-circuit where each gate has
fan-out at most one. We show that if $G$ has treedepth $t$ and maximum degree
$d$, then any MWIS-formula of $G$ has $2^{\Omega(t/d)}$ gates. It follows that
treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded
degree graphs and planar graphs, and treedepth characterizes optimal
MWIS-formulas up to polynomials for all bounded degree graphs.
