Say we are solving a tree decomposition problem, e.g. given a graph $G = (V, E)$ we try to find a chordal graph $H$ such that $V(H) = V(G)$, $E(G) \in E(H)$ and the maximal clique in $H$ is minimal among all possible $H$.

This problem is known to be NP-hard. For other/better definitions of tree decomposition/treewidth see Wikipedia

Is there a way to reduce treewidth to some other NP problems, especially Maximum Independent Set/Maximum clique/SAT or similar ones?

I found a lot of results of sort "if a graph has bounded treewidth, then problem XXX has a polynomial solution", but nothing like "if we can solve XXX, then we can find the tree decomposition"


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.