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

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

  • 3
    $\begingroup$ The grid minor theorem has been improved. arxiv.org/abs/1901.07944 $\endgroup$ – Chandra Chekuri Nov 4 '19 at 15:05
  • $\begingroup$ 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). $\endgroup$ – Chandra Chekuri Nov 4 '19 at 15:07
  • $\begingroup$ Where does the number 37 enter the scene? Is this a constant in the statement of the grid minor theorem? $\endgroup$ – Hermann Gruber Nov 4 '19 at 18:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Nov 5 '19 at 2:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Artur Riazanov Nov 5 '19 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.