<p>In the case of pathwidth, reposting here a comment made to me by email by Benjamin Rossman back in 2020 (see also the comments to the answer <a href="https://cstheory.stackexchange.com/a/38943">https://cstheory.stackexchange.com/a/38943</a>):</p>
<blockquote>
<p>Every graph G of pathwidth <span class="math-container">$k$</span> contains a subgraph of degree <span class="math-container">$\leq 3$</span> with pathwidth <span class="math-container">$\tilde{\Omega}(\sqrt k)$</span>. Indeed, from the recent result <a href="https://arxiv.org/pdf/2008.00779.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2008.00779.pdf</a>, every graph of
pathwidth <span class="math-container">$\Omega(k)$</span> must either have treewidth <span class="math-container">$\Omega(\sqrt k)$</span>, so by
the Chekuri-Chuzhoy sparsification result it contains a subgraph of degree 3 and treewidth
<span class="math-container">$\tilde{\Omega}(\sqrt k)$</span>; or must contain a subdivision of the complete binary
tree of height <span class="math-container">$\Omega(\sqrt k)$</span>, which serves as a witnessing subgraph of
degree 3 and pathwidth <span class="math-container">$\Omega(\sqrt k)$</span>.</p>
</blockquote>
<p>The question of achieving <span class="math-container">$\tilde{\Omega}(k)$</span> for pathwidth is open, as far as we know.</p>

CC BY-SA 4.0
2021-07-28T17:11:24.680Z
2021-07-28T17:11:24.680Z
Antoine Amarilli 'a3nm'
<p>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$. 
<a href="https://arxiv.org/abs/1410.1016" rel="noreferrer">https://arxiv.org/abs/1410.1016</a> The proof is shorter than the one 
for grid minors but it is still not that that easy and builds on several previous 
tools.</p>

<p>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. <a href="https://arxiv.org/abs/0809.0724" rel="noreferrer">https://arxiv.org/abs/0809.0724</a></p>

<p>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. </p>

CC BY-SA 3.0
2017-08-29T21:16:33.337Z
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
CC BY-SA 3.0
2017-08-30T14:37:37.207Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-08-30T14:44:46.220Z
Again, this is very helpful, thank you. It's interesting that the question for linear treewidth is still open. (That said, if I understand correctly, Conjecture 1.2 in your sparsifier paper is about a slightly different problem: it requires the subgraph to be a subdivision of some H of polynomial size in k, whereas I'm not asking for this and just want the subgraph to have constant degree.) One last thing: do you know whether anything is known about this open problem but for pathwidth rather than treewidth? Thanks again!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-08-31T01:01:40.080Z
@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
CC BY-SA 3.0
2017-09-12T06:53:34.390Z
Thanks for you explanations about the status of linear threewidth, and thanks also for the pathwidth sparsification explanations. The last thing that you mentioned is the kind of results we would have needed; too bad that the question is still open. In any case, thanks a lot again for your explanations!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-08-29T14:08:04.653Z
2017-08-29T21:53:38.750Z
2017-08-29T21:53:38.750Z
Chandra Chekuri
<p>I am given a graph $G$ with <a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">treewidth</a> $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)$.</p>

<p>Obviously we should take $d \geq 3$ as there are no high treewidth graphs with maximal degree $&lt;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 <a href="https://arxiv.org/abs/1305.6577" rel="noreferrer">grid minor extraction result</a> (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 <em>any</em> 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 <a href="https://arxiv.org/abs/1602.02629" rel="noreferrer">known</a> 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, <strong>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$?</strong></p>

<p>I'm also interested in the exact same question for <a href="https://en.wikipedia.org/wiki/Pathwidth" rel="noreferrer">pathwidth</a> rather than treewidth. For pathwidth I don't know any analogue to grid minor extraction, so the problem seems even more mysterious...</p>

<co.combinatorics><treewidth><graph-minor><bounded-degree>
Finding subgraphs with high treewidth and constant degree
Antoine Amarilli 'a3nm'
# Finding subgraphs with high treewidth and constant degree

(Asked by: username_0 on 2017-08-28)

I am given a graph $G$ with [treewidth](https://en.wikipedia.org/wiki/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](https://arxiv.org/abs/1305.6577) (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](https://arxiv.org/abs/1602.02629) 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](https://en.wikipedia.org/wiki/Pathwidth) rather than treewidth. For pathwidth I don't know any analogue to grid minor extraction, so the problem seems even more mysterious...

**Tags:** co.combinatorics, treewidth, graph-minor, bounded-degree


---

## 2 answers

### Answer by username_1 on 2017-08-29. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_1**: 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)$.  
> **username_0**: 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.  
> **username_0**: Again, this is very helpful, thank you. It's interesting that the question for linear treewidth is still open. (That said, if I understand correctly, Conjecture 1.2 in your sparsifier paper is about a slightly different problem: it requires the subgraph to be a subdivision of some H of polynomial size in k, whereas I'm not asking for this and just want the subgraph to have constant degree.) One last thing: do you know whether anything is known about this open problem but for pathwidth rather than treewidth? Thanks again!  
> **username_1**: @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.  
> **username_0**: Thanks for you explanations about the status of linear threewidth, and thanks also for the pathwidth sparsification explanations. The last thing that you mentioned is the kind of results we would have needed; too bad that the question is still open. In any case, thanks a lot again for your explanations!  

---

### Answer by username_0 on 2021-07-28. Score: 1

In the case of pathwidth, reposting here a comment made to me by email by Benjamin Rossman back in 2020 (see also the comments to the answer <https://cstheory.stackexchange.com/a/38943>):

> Every graph G of pathwidth $k$ contains a subgraph of degree $\leq 3$ with pathwidth $\tilde{\Omega}(\sqrt k)$. Indeed, from the recent result <https://arxiv.org/pdf/2008.00779.pdf>, every graph of
> pathwidth $\Omega(k)$ must either have treewidth $\Omega(\sqrt k)$, so by
> the Chekuri-Chuzhoy sparsification result it contains a subgraph of degree 3 and treewidth
> $\tilde{\Omega}(\sqrt k)$; or must contain a subdivision of the complete binary
> tree of height $\Omega(\sqrt k)$, which serves as a witnessing subgraph of
> degree 3 and pathwidth $\Omega(\sqrt k)$.

The question of achieving $\tilde{\Omega}(k)$ for pathwidth is open, as far as we know.


---

