12
$\begingroup$

Is it possible to unite two $n$-vertex trees such that the resulting graph has bounded tree-width?

Formally, does there exists a constant $k$ such that given two $n$-vertex trees $T_1$ and $T_2$ there exist labeled trees $T_1'=([n], E_1)$ and $T_2' =([n],E_2)$ with $T_1' \simeq T_1$, $T_2' \simeq T_2$ and $$ \texttt{treewidth} (T_1' \cup T_2') \leq k, $$ where $T_1' \cup T_2' = ([n], E_1 \cup E_2)$.

Special cases

  1. $T_1 \simeq P_n$ and $T_2 \simeq P_n$. While one can 'construct' a grid out of two large paths (and a grid has 'large' tree-width), $T_1$ and $T_2$ can be united into a path $P_n$ (which has treewidth 1).
  2. $T_1$ is a star, $T_2$ is an arbitrary tree. In this case, no matter how we unite the trees we get a chordal graph with maximum clique size 3, and therefore of tree-width 2.
  3. It is also possible to unite a path with an arbitrary tree into a graph of bounded tree-width. But it is not clear if this is always possible for a pair of arbitrary trees.
Improve this question
$\endgroup$
8
  • $\begingroup$ How big can the tree width be if you're trying to make it large? You can form $K_4$ as the union of two trees. But how much bigger could we make the tree width of the union? $\endgroup$
    – Pat Devlin
    Dec 30, 2016 at 23:56
  • $\begingroup$ The tree-width can be large (it is not important now), but it should be bounded by some constant $k$ for every pair of trees. In fact I want to minimize the tree-width of a union, but not to maximize. $\endgroup$
    – Victor
    Dec 31, 2016 at 1:08
  • $\begingroup$ Just to clarify: I was asking if the treewidth could be made arbitrarily large by the union of two poorly-put-together trees. I ask to rule out an avenue of attack. I now see that in comment 1 you address this by weaving (or perhaps knitting or crocheting...) two paths into a large grid. $\endgroup$
    – Pat Devlin
    Dec 31, 2016 at 13:05
  • 1
    $\begingroup$ On the other end of things, do you have any trees that would show that we would need $k \geq 3$? $\endgroup$
    – Pat Devlin
    Dec 31, 2016 at 13:19
  • 1
    $\begingroup$ I really like this question! To the third point: I think you can always make the union outer planar, is that what you had in mind? I had my computer perform a brute-force search through all pairs of trees on 10 vertices and could't find an instance where a tree width greater than 2 was necessary. (The permutations were generated randomly until one was found where the resulting tree width was 2. On average, it took 22.5 'guesses', which is surprisingly small in my opinion.) $\endgroup$
    – monkeymaths
    Apr 7, 2017 at 13:07

1 Answer 1

Reset to default
2
$\begingroup$

It is shown in Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev: "The treewidth and pathwidth of graph unions" that the general question has a negative answer.

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.