In graph theory, a partial k-tree is a type of graph, defined either as a subgraph of a k-tree or as a graph with treewidth at most k.[1] Many NP-hard combinatorial problems on graphs are solvable in polynomial time when restricted to the partial k-trees, for bounded values of k.