How to compute treewidth

It is NP-hard in general — and entirely practical anyway.

The exact picture

Deciding whether tw(G) ≤ k is NP-complete in general. But it is fixed-parameter tractable in k: Bodlaender's algorithm decides it in time linear in the number of vertices for any fixed k, with a constant that is (famously) astronomical. In practice nobody runs Bodlaender's algorithm — it is an existence proof that the problem is FPT.

What people actually run

For real graphs the toolkit is: elimination-ordering heuristics (min-degree, min-fill) for fast upper bounds; the minor-min-width and MMD+ heuristics for lower bounds; and exact solvers based on positive-instance driven dynamic programming or SAT encodings for moderate graphs. The PACE challenge solvers handle graphs with thousands of vertices.

An elimination ordering is the practical handle: eliminating vertices one at a time, connecting their neighbors as you go, produces a chordal completion whose largest clique minus one is an upper bound on treewidth. Min-fill — eliminate the vertex that adds the fewest fill edges — is the default heuristic for a reason.