# How much does treewidth changes after removal of a path?

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:

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})$$?

• The grid minor theorem has been improved. arxiv.org/abs/1901.07944 – Chandra Chekuri Nov 4 '19 at 15:05
• 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 Nov 4 '19 at 15:07
• Where does the number 37 enter the scene? Is this a constant in the statement of the grid minor theorem? – Hermann Gruber Nov 4 '19 at 18:34
• 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 Nov 5 '19 at 2:36
• 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 eccc.weizmann.ac.il/report/2019/020 which uses grid minor theorem. – Artur Riazanov Nov 5 '19 at 7:38