# Finding subgraphs with high treewidth and constant degree

I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth is as high as possible. Formally my problem is the following: having chosen a degree bound $d \in \mathbb{N}$, what is the "best" function $f : \mathbb{N} \to \mathbb{N}$ such that, in any graph $G$ with treewidth $k$, I can find (hopefully efficiently) a subgraph $H$ of $G$ with maximal degree $\leq d$ and treewidth $f(k)$.

Obviously we should take $d \geq 3$ as there are no high treewidth graphs with maximal degree $<3$. For $d = 3$ I know that you can take $f$ such that $f(k) = \Omega(k^{1/100})$ or so, by appealing to Chekuri and Chuzhoy's grid minor extraction result (and using it to extract a high-treewidth degree-3 graph, e.g., a wall, as a topological minor), with the computation of the subgraph being feasible (in RP). However, this is a very powerful result with an elaborate proof, so it feels wrong to use it for what looks like a much simpler problem: I would just like to find any constant-degree, high-treewidth subgraph, not a specific one like in their result. Further, the bound on $f$ is not as good as I would have hoped. Sure, it is known that it can be made $\Omega(k^{1/20})$ (up to giving up efficiency of the computation), but I would hope for something like $\Omega(k)$. So, is it possible to show that, given a graph $G$ of treewidth $k$, there is a subgraph of $G$ with constant degree and linear treewidth in $k$?

I'm also interested in the exact same question for pathwidth rather than treewidth. For pathwidth I don't know any analogue to grid minor extraction, so the problem seems even more mysterious...

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. https://arxiv.org/abs/1410.1016 The proof is shorter than the one for grid minors but it is still not that that easy and builds on several previous tools.
Suppose you settle for an easier target - degree 4 and treewidth $\Omega(k^{1/4})$ then you can get it much more easily via result of Reed and Wood on grid-like minors. https://arxiv.org/abs/0809.0724
Another easy result you can obtain is the following which is a starting point for some of the more involved proofs. You can get a subgraph of degre $\log^2(k)$ and treewidth $\Omega(k/\mathsf{polylog}(k))$. You can see the treewidth sparsifier paper for the argument to achieve this.
• Additional comment. Whether one can get a subgraph with $\Omega(k)$ treewidth and constant degree is a very interesting open problem. We ask this question in the treewidth sparsifier paper but don't have a good sense of the right answer. One interesting graph that Bart Jansen asked about is the hypercube on $n$ nodes which has treewidth $\Theta(n/\log n)$ and initial degree $\Theta(\log n)$. – Chandra Chekuri Aug 29 '17 at 21:16
• Thanks for pointing to Reed and Wood! I'll fill out the details. Thm 1.2 of their paper says that a graph G with treewidth $\Omega(l^4 polylog(l))$ contains a grid-like-minor of order l. Now a grid-like-minor M is a subgraph of G formed of paths with a bipartite intersection graph H, so every vertex in M belongs to at most 2 paths of M (otherwise it's a triangle in H), hence M has maximal degree 4. Further, M has treewidth $\Omega(l)$: indeed any tree dec of M of width k yields a tree dec of H of width <= 2k (replacing each vertex by its member paths, at most 2), and H has $K_l$ as a minor. – a3nm Aug 30 '17 at 14:37
• @a3nm why are you surprised that the question of linear treewidth is open? We don't currently have a constant factor approximation for treewidth. Regarding pathwidth, right now the only way to approximate pathwidh is via the relationship between treewdith and pathwidth which shows $tw(G) \le pw(G) \le O(\log n) tw(G)$. Via the treewidth sparsification one can also get pathwidth sparsification but we lose a log n factor. It would be nice if this was only log pw(G) factor but I am not sure how to do it or whether it is known. – Chandra Chekuri Aug 31 '17 at 1:01