0
$\begingroup$

On the page 6 of the paper Simulating quantum circuits by contracting tensor network author wrote about the equivalence of treewidth of a Graph and its induced width where the treewidth is defined through the tree decompositions and the induced width - as the maximum degree of a graph vertex at the time of its elimination. Unfortunately, the referenced survey (5) doesn't provide enough details for me to understand it. What is a good proof of this fact?

$\endgroup$

1 Answer 1

1
$\begingroup$

If a graph $G$ has treewidth $\leq k$, then it is a subgraph of a $k$-tree. By taking a perfect elimination sequence, the graph $G$ turns our to have induced width $\leq k$.

Conversely, suppose a graph $G$ has induced width $\leq k$. Let $\pi$ be a elimination ordering of $G$. Let $H$ be a graph with the same vertices of $G$ and two vertices of $H$ are connected iff they are once connected in the elimination ordering process. The graph $H$ is a $k$-tree and contains $G$ as a subgraph (because all the edges of $G$ are present in the beginning of the elimination ordering process). So $G$ is contained in a $k$-tree and thus has treewidth $\leq k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.