patternMinor
How does treewidth behave under graph minor operations?
Viewed 0 times
treewidthoperationsbehavegraphminorunderdoeshow
Problem
It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.
Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3).
Of particular interest for me is the question whether said decrease can always be bounded by some constant.
Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3).
Of particular interest for me is the question whether said decrease can always be bounded by some constant.
Solution
The decrease in tree width of any of the three operations will be 0 or 1. The proof is simple (I will take the case of the vertex deletion).
Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.
Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.
Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$. Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.
Let $G$ be the original graph and $G' = G - v$ be the graph obtained by deleting $v$.
Let $T'$ be an optimal tree decomposition of $G'$, with $\text{tw}(G') = w'$.
Now, construct $T$ from $T'$ by adding $v$ to every bag of $T'$. Clearly, $T$ is a tree decomposition for $G$ with width $\text{tw}(G) \leq \text{tw}(T) = 1 + \text{tw}(G') = 1 + w'$.
Context
StackExchange Computer Science Q#104467, answer score: 4
Revisions (0)
No revisions yet.