NP-Complete:

1.Edge-disjoint paths (Nishizeki,Vygen,Zhou) is NP-complete for graphs of treewidth 2.

Input: A graph G = (V, E) and pairs {s_i ,t_i}

Output: find k edge-disjoint paths Pi in G such that P_i connects s_i and t_i .

2.Calculating treewidth ≤ k (Arnborg, Corneil, Proskurowski) 

Input: A graph G and integer k

Output: Decide whether tw(G) ≤ k

NP-hard:

1.Weighted coloring(McDiarmid & Reed) is NP-hard for graphs of treewidth 

Input: a graph G = (V, E) and a weight function w : V \to NN

Output: a weighted k-coloring, i.e., a function c : V \to 2^[k] such that |c(v)| = w(v) for all v ∈ V and c(u) \cap c(v) = \emptyset for all uv\in E.

2.Determining the treewidth of an arbitrary graph.

3.Finding the largest clique in Graph is NP-hard, however a maximal denset subgraph can be computed in linear time