6
$\begingroup$

Treewidth has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small ``naive treewidth''.

Naive treewidth is defined as follows. Let $G=(V,E)$ be a graph. We say that $G$ has naive treewidth $k$ if there exists a partition $V_1 \sqcup V_2 \sqcup \ldots \sqcup V_m = V$ such that $|V_i| \le k$ and a tree $T = ([m], E_T)$ such that for every $(u,v) \in E$ either $u,v \in V_i$ for some $i \in [m]$ or $(u,v) \in V_i \times V_j$ such that $(i,j) \in E_T$.

If $T$ is a path than we say that $G$ has naive pathwidth $k$.

For naive pathwidth it is easy to see that it can be much larger than pathwidth. Consider a full binary tree with $2^k$ leaves. It has pathwidth $k-1$. On the other hand notice that if naive pathwidth of a graph is $\le t$ than the partition contains at least ${|V| \over t}$ blocks. Thus there exists a path in $G$ of length at least ${|V| \over t} - 1$. Since the longer path in the full binary tree of height $k$ is $2k$, naive pathwidth of the full binary tree is at least ${2^k \over 2k}$.

Notice that instead of the full binary tree it was possible to use a tree with one vertex connected to the remaining $|V|-1$ vertices which gives even better separation. The reason I've used the binary tree is that for my purposes all graphs have constant degree.

My questions are:

  1. For a graph with small pathwidth (and constant degree if it is needed) can it be shown that it has small naive treewidth? If it is not true, how the counterexample looks like?
  2. The same question for a graph with small treewidth.

Update: for arbitrary degrees there is a separation between treewidth and naive treewidth. The example is a path of length $n$ and a vertex connected to all vertices of the path. Treewidth of such graph is $2$ and naive treewidth is $\Omega(\sqrt{n})$. The proof goes like this: consider the block $B$ containing the vertex of degree $n$. Assume that this block contains at most $\sqrt{n} / 2$ vertices. Then there exists a path in $G - B$ containing at least $2 \sqrt{n}$. Notice that in $T$ all the blocks should be connected to $B$. Thus this path of length $2 \sqrt{n}$ must be contained in a single block.

$\endgroup$
8
$\begingroup$

Your parameter "naive treewidth" is known as tree-partition-width in the literature. It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-width. See [Wood 2009].

Note that your example in the update actually has pathwidth 2.

[Wood 2009] David R. Wood. On tree-partition-width. European Journal of Combinatorics 30 (2009) 1245-1253. https://doi.org/10.1016/j.ejc.2008.11.010 (also on arXiv https://arxiv.org/abs/math/0602507)

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot! I thought that full binary tree with the path going through all leaves might provide a separation, but apparently that is not the case. Is there a simple tree-partition-width decomposition? $\endgroup$ – Artur Riazanov Mar 20 at 16:08
  • 1
    $\begingroup$ That's a good example.... I don't have a quick answer for it. We may read the proof in [Wood 2009] (or the references therein). $\endgroup$ – Yota Otachi Mar 21 at 3:07

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.