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
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