<p>Let <span class="math-container">$G$</span> be a graph such that <span class="math-container">$\mathrm{tw}(G)=t$</span>. Let <span class="math-container">$t' = \min\limits_{u,v \in V(G)} \max\limits_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$</span>. Then how small <span class="math-container">$t'$</span> can be?</p>

<p>My observation is that <span class="math-container">$t' = \Omega(t^{1/10})$</span> because of grid minor theorem (<a href="https://arxiv.org/abs/1901.07944" rel="nofollow noreferrer">https://arxiv.org/abs/1901.07944</a>). Indeed, let <span class="math-container">$H$</span> be a grid minor of <span class="math-container">$G$</span> of size at least <span class="math-container">$t^{1/10}$</span>. Then pick any shortest path from <span class="math-container">$u'$</span> to <span class="math-container">$v'$</span> in <span class="math-container">$H$</span> where <span class="math-container">$u'$</span> is the closest to <span class="math-container">$u$</span> vertex that was not removed during the construction of <span class="math-container">$H$</span>, and <span class="math-container">$v'$</span> is the closest one to <span class="math-container">$v$</span>. Then we can pick a shortest path from <span class="math-container">$u$</span> to <span class="math-container">$u'$</span> then the shortest path from <span class="math-container">$u'$</span> to <span class="math-container">$v'$</span> in <span class="math-container">$H$</span> and translate it to a path in <span class="math-container">$G$</span> reversing edge contractions and then take the shortest path from <span class="math-container">$v'$</span> to <span class="math-container">$v$</span>. One may notice that after the removal of such path the resulting graph still has a grid minor of size <span class="math-container">$\Omega(t^{1/10})$</span> and thus treewidth of size <span class="math-container">$\Omega(t^{1/10})$</span>.</p>

<p>Although the strategy of removing the shortest path between <span class="math-container">$u$</span> and <span class="math-container">$v$</span> doesn't always work. The counterexample is the following graph:
<a href="https://i.sstatic.net/AShkt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/AShkt.png" alt="enter image description here"></a></p>

<p>Black edges represent paths of <span class="math-container">$n^3$</span> edges, red edges represent single edge. That way red path is the shortest path between its ends and its removal turns the grid-like graph into a tree.</p>

<p>So my question is, is it possible to prove better lower bounds on <span class="math-container">$t'$</span> than <span class="math-container">$\Omega(t^{1/10})$</span>? </p>

CC BY-SA 4.0
2019-11-04T15:05:36.913Z
The grid minor theorem has been improved. https://arxiv.org/abs/1901.07944
Chandra Chekuri
CC BY-SA 4.0
2019-11-04T15:07:37.267Z
Also, the phrasing of your question should be improved. I assume that you want to minimize over all choices of u,v in the graph. So what you want is \min{u,v \in V} \max_{\text{P is path from u to v} tw(G-P).
Chandra Chekuri
CC BY-SA 4.0
2019-11-04T18:34:31.527Z
Where does the number 37 enter the scene? Is this a constant in the statement of the grid minor theorem?
Hermann Gruber
CC BY-SA 4.0
2019-11-04T18:43:22.457Z
Chandra, thank you! You are right, I am interested in the worst possible case of $u$ and $v$.
Artur Riazanov
CC BY-SA 4.0
2019-11-04T18:44:45.383Z
Hermann. yes, $t^{1/37}$ comes from an apparently outdated version of the grid minor theorem.
Artur Riazanov
CC BY-SA 4.0
2019-11-05T02:36:30.883Z
I wonder if one may be able to prove that $t' = \Omega(t/polylog(t))$. Julia Chuzhoy will probably be able to see it quickly. Worth writing to her. Also, I am curious about the motivation for the question.
Chandra Chekuri
CC BY-SA 4.0
2019-11-05T07:00:14.150Z
Seems like $t' = \Omega(t)$ for 2-connected graphs, if I am not mistaken it follows from the main statement of the section 3 of https://www.sciencedirect.com/science/article/pii/S0095895684710732
Artur Riazanov
CC BY-SA 4.0
2019-11-05T07:38:22.440Z
Chandra, turns out that proof complexity of a Tseitin formula (CNF-encoding of systems of linear equations modulo 2 such that each variable appears in exactly two equations) can be nicely characterized in terms of tree-width of the (equations, $\{uv \mid \text{equations } u \text{ and } v \text{ share a variable}\}$) graph for many proof systems. The answer of this question helps to improve the last result of https://eccc.weizmann.ac.il/report/2019/020/ which uses grid minor theorem.
Artur Riazanov
<graph-theory><treewidth>
How much does treewidth changes after removal of a path?
Artur Riazanov
# How much does treewidth changes after removal of a path?

(Asked by: username_0 on 2019-11-03)

Let $G$ be a graph such that $\mathrm{tw}(G)=t$. Let $t' = \min\limits\_{u,v \in V(G)} \max\limits\_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$. Then how small $t'$ can be?

My observation is that $t' = \Omega(t^{1/10})$ because of grid minor theorem (<https://arxiv.org/abs/1901.07944>). Indeed, let $H$ be a grid minor of $G$ of size at least $t^{1/10}$. Then pick any shortest path from $u'$ to $v'$ in $H$ where $u'$ is the closest to $u$ vertex that was not removed during the construction of $H$, and $v'$ is the closest one to $v$. Then we can pick a shortest path from $u$ to $u'$ then the shortest path from $u'$ to $v'$ in $H$ and translate it to a path in $G$ reversing edge contractions and then take the shortest path from $v'$ to $v$. One may notice that after the removal of such path the resulting graph still has a grid minor of size $\Omega(t^{1/10})$ and thus treewidth of size $\Omega(t^{1/10})$.

Although the strategy of removing the shortest path between $u$ and $v$ doesn't always work. The counterexample is the following graph:
[![enter image description here](https://i.sstatic.net/AShkt.png)](https://i.sstatic.net/AShkt.png)

Black edges represent paths of $n^3$ edges, red edges represent single edge. That way red path is the shortest path between its ends and its removal turns the grid-like graph into a tree.

So my question is, is it possible to prove better lower bounds on $t'$ than $\Omega(t^{1/10})$?

**Tags:** graph-theory, treewidth

> **Comments:**
> **username_1**: The grid minor theorem has been improved. https://arxiv.org/abs/1901.07944  
> **username_1**: Also, the phrasing of your question should be improved. I assume that you want to minimize over all choices of u,v in the graph. So what you want is \min{u,v \in V} \max_{\text{P is path from u to v} tw(G-P).  
> **username_2**: Where does the number 37 enter the scene? Is this a constant in the statement of the grid minor theorem?  
> **username_0**: Chandra, thank you! You are right, I am interested in the worst possible case of $u$ and $v$.  
> **username_0**: Hermann. yes, $t^{1/37}$ comes from an apparently outdated version of the grid minor theorem.  
> **username_1**: I wonder if one may be able to prove that $t' = \Omega(t/polylog(t))$. Julia Chuzhoy will probably be able to see it quickly. Worth writing to her. Also, I am curious about the motivation for the question.  
> **username_0**: Seems like $t' = \Omega(t)$ for 2-connected graphs, if I am not mistaken it follows from the main statement of the section 3 of https://www.sciencedirect.com/science/article/pii/S0095895684710732  
> **username_0**: Chandra, turns out that proof complexity of a Tseitin formula (CNF-encoding of systems of linear equations modulo 2 such that each variable appears in exactly two equations) can be nicely characterized in terms of tree-width of the (equations, $\{uv \mid \text{equations } u \text{ and } v \text{ share a variable}\}$) graph for many proof systems. The answer of this question helps to improve the last result of https://eccc.weizmann.ac.il/report/2019/020/ which uses grid minor theorem.  

---

## 0 answers

