Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 < \alpha < 1$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ FYI: There is another question for graphs with treewidth $o(n^{1/2})$: cstheory.stackexchange.com/questions/33753/… $\endgroup$– delete000Feb 6, 2018 at 19:41
-
5$\begingroup$ If you don't impose more restrictions then just take a clique with $n^{\alpha}$ vertices and connect it to a line with $n-n^{\alpha}$ vertices. Then the treewidth is $\Theta(n^{\alpha})$. To avoid such trivial answers, it would be good to reformulate the question to something like. "Which natural (well studied) classes of graphs have treewidth $n^{\alpha}$?" But even with such rephrasing it is very easy to come up with artificial examples. $\endgroup$– Mateus de Oliveira OliveiraFeb 6, 2018 at 21:33
-
$\begingroup$ @MateusdeOliveiraOliveira Done. $\endgroup$– delete000Feb 7, 2018 at 3:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent Quanrud) on low density graphs: http://sarielhp.org/p/14/low_density/low_density.pdf. Sorry for the shameless self promotion, etc.
answered Feb 7, 2018 at 17:40
-
1$\begingroup$ You got that footnote into the published version! You, sir, have my eternal respect. $\endgroup$ Feb 7, 2018 at 19:16
-
$\begingroup$ Thank you. You are right! The footnote is in the official SICOMP version... $\endgroup$ Feb 8, 2018 at 5:18
-
2$\begingroup$ BTW, the bible on such things is the book Sparsity: springer.com/us/book/9783642278747 $\endgroup$ Feb 8, 2018 at 5:24
-
$\begingroup$ Thanks, digging into it now. Regarding your work: do sublinear separators in these classes of graphs imply subexponential exact algorithms, in analogy to planar graphs with $O(\sqrt{n})$ separators, at least for some classes of problems? $\endgroup$ Feb 8, 2018 at 13:06
-
$\begingroup$ Yes. They should. We didn't look into that because (A) the paper is already long, (B) at this point, it seems like one should just state such algorithms for polynomial expansion graphs (i.e., graphs that have hereditary sublinear separators), and (C) we did not have any interesting example of such algorithms. $\endgroup$ Feb 8, 2018 at 16:57