treewidth
Many problems that are NP-hard on general graphs become easy on trees, because a tree has no tangled cycles — you can solve it by sweeping from the leaves up to the root, combining sub-answers as you go (that is tree DP). Real graphs are not trees, but some are ALMOST trees — they only have a few small, local tangles. Treewidth is a single number that measures exactly how far a graph is from being a tree: 0 or 1 for actual trees, small for nearly-tree-like graphs, large for densely interconnected ones. The smaller the treewidth, the more the tree-style attack still works.
The precise definition uses a tree decomposition: you cover the graph with overlapping 'bags' of vertices, arranged in a tree shape, obeying two rules — every edge of the graph has both its endpoints together in some bag, and for every vertex, all the bags containing it form a connected sub-tree. The width of a decomposition is (size of its largest bag) minus 1, and the treewidth is the smallest width over all valid decompositions. Intuitively, each bag is a 'separator' — a small bottleneck through which the rest of the graph communicates. Because bags are small (size at most treewidth + 1), you can run dynamic programming over the decomposition tree: process bags from leaves to root, and at each bag remember a partial answer for every way the few vertices in that bag could behave. This gives algorithms running in time f(treewidth) * n — so a graph of bounded treewidth is solved in linear time even for NP-hard properties.
Treewidth matters because it is one of the most powerful parameters in all of parameterized complexity: bound it, and a vast catalogue of otherwise-hard problems (independent set, dominating set, coloring, Hamiltonian path, and any property expressible in a certain logic, by Courcelle's theorem) become tractable. It captures why problems are easy on series-parallel graphs, control-flow graphs of structured code, and many real networks. The honest caveats: the dynamic program's cost typically grows EXPONENTIALLY in the treewidth (often around 2^treewidth or worse per bag), so the trick only pays off when treewidth is small — and many natural graphs (large grids, dense graphs, expanders) have large treewidth and gain nothing; computing the treewidth exactly is itself NP-hard, though good approximations and FPT algorithms for it exist.
A tree has treewidth 1; a single cycle has treewidth 2; a series-parallel graph has treewidth 2. An n-by-n grid has treewidth n, which is large. On a graph of treewidth t, maximum independent set is solved by DP over the decomposition in time about 2^t * n: bound t and an NP-hard problem becomes linear-time; let t grow and the 2^t factor wipes out the gain.
Treewidth = how tree-like a graph is; small treewidth lets tree-DP solve NP-hard problems in f(tw)*n.
The DP cost usually grows EXPONENTIALLY in treewidth (often ~2^tw per bag), so small treewidth is essential — large grids, dense graphs and expanders have large treewidth and gain nothing. Computing treewidth exactly is itself NP-hard. Treewidth 1 means a tree (or forest), not treewidth 0.