Def: die Baumweite (tree width):
leider ...
TW = {(G, k) | tw(G)k} NPC,
aber ...für jedes feste k : TWk = {G | tw(G)k} P (sogar Linearzeit, aber mit abenteuerlichen Faktoren)
Die Algorithmen zur nachträglichen Feststellung der Baumweite bzw. eines Eliminationsschemas sind unpraktisch ... aber oft gar nicht nötig: in vielen Anwendungen kann man ein Eliminationsschema schon von vornherein in der Eingabe des Algorithmus voraussetzen, z. B. für Graphen, die durch die Art ihrer Erzeugung (also genetisch) kleine Baumweite haben.