Many discrete optimization problems are both very difficult and important in a range of applications in engineering, computer science and operations re­search. 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 NP-hard problems, restricted domains of problems' i­stances are being studied, with hopes that some such modified problems would admit efficient (polynomially bounded) solution algorithms. We survey investigations of the complexity behavior of 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 char­acterization 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.