10
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Chandra Chekuri
    Aug 29, 2017 at 21:16
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Aug 30, 2017 at 14:37
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Aug 30, 2017 at 14:44
  • $\begingroup$ @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. $\endgroup$
    – Chandra Chekuri
    Aug 31, 2017 at 1:01
  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Sep 12, 2017 at 6:53
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.