9
$\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...

$\endgroup$
12
$\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.

$\endgroup$
  • 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 '17 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 '17 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 '17 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 '17 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 '17 at 6:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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