2
$\begingroup$

Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ be the graph obtained from $G'$ where for every leaf $x$, an edge between $x_1, x_2$ is introduced.

I am interested in the treewidth of $G$. I conjecture that it is $O(\log(n))$ (start at the root of one copy of a tree, then first visit the left subtree and recurse until the root node of the other tree is reached, we always need to keep track of a path of length at most $\log(n)$). First, is this correct? Second, how can I prove a LB on the treewidth of this graph?

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ What would prevent this graph from being series-parallel? $\endgroup$ – Gamow Mar 21 '17 at 14:24
  • $\begingroup$ Thanks, I am new to treewidth and I missed this. The treewidth is hence 2. I would still be interested to see how the actual decomposition looks like. $\endgroup$ – Chris Mar 21 '17 at 14:51
  • $\begingroup$ For graphs up to 150 vertices you can use treedecompositions.com to find and visualize a reasonable heuristic decomposition. $\endgroup$ – Fasermaler Mar 21 '17 at 20:12
5
$\begingroup$

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT." Theoretical Computer Science 351.3 (2006): 296-302. The graph structure they use unifies leaves with the same label (rather than putting an edge between them), but their graph can be obtained from yours by suppressing degree-2 vertices, and this does not impact upon the treewidth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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