Skip to main content
2 of 5
deleted 5 characters in body
qbit-
  • 71
  • 2

Treewidth problem reductions

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/3-SAT or similar ones?

I found a lot of results of sort "if a graph has a bounded treewidth, then problem XXX has a polynomial solution", but nothing like an algorithm to find treewidth from a solved NP problem instance

qbit-
  • 71
  • 2