Many discrete optimization problems are both very
difficult and important in a range of applications in
engineering, computer science and operations research.
In recent years, a generally accepted measure of a
problem's difficulty became a worst-case, asymptotic
growth complexity characterization. Because of the
anticipated at least exponential complexity of any
solution algorithm for members in the class of `\cal
NP`-hard problems, restricted domains of problems'
instances are being studied, with hopes that some such
modified problems would admit efficient (polynomially
bounded) solution algorithms. We survey investigations
of the complexity behaviour of \cal NP-hard discrete
optimization problems on graphs restricted to different
generalizations of trees (cycle-free, connected
graphs). The scope of this survey includes definitions
and algorithmic characterization of families of graphs
with tree-like structures that may guide the
development of efficient solution algorithms for
difficult optimization problems and the development of
such solution algorithms.
