7
$\begingroup$

Treewidth :

1) By chordal graphs : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$.

2) By tree decomposition :

A tree decomposition of $G = (V , E)$ consists of a tree $T$ (on a different node set from $G$), and a subset $V_t ⊆ V$ associated with each node $t$ of $T$. (We will call these subsets $V_t$ the “pieces” of the tree decomposition.) We will sometimes write this as the ordered pair $(T , {V_t : t ∈ T })$. The tree T and the collection of pieces $\{V_t : t ∈ T \}$ must satisfy the following three properties

(Node Coverage) Every node of $G$ belongs to at least one piece $V_t$.

(Edge Coverage) For every edge $e$ of $G$, there is some piece $V_t$ containing both ends of $e$.

(Coherence) Let $t_1, t_2,$ and $t_3$ be three nodes of $T$ such that $t_2$ lies on the path from $t_1$ to $t_3$. Then, if a node $v$ of $G$ belongs to both $V_{t_{1}}$ and $V_{t_{3}}$, it also belongs to $V_{t_2}$

So we define the width of a tree decomposition $(T , {V_t })$ to be one less than the maximum size of any piece $V_t$ (over all $t$): $$width (T , {V_t}) = max |V_t| − 1$$

Claim 1: If size of largest clique in a chordal decomposition of graph is say $k$ then by tree decomposition we will get tree width $k$

Proof : let us assume that largest clique size in chordal completion graph is $k$, so there exist a bag (subset of vertices of graph) that contain the clique ( due to edge coverage ). so we are done.

claim 2 : If tree width is $k$ by tree decomposition method then by chordal completion method also is $k$

Question : How to prove the claim 2 ?High level proof will be welcomed.

$\endgroup$
  • $\begingroup$ About the proof of claim 1: It is indeed clear that the chordal completion has treewidth k, from your proof it is not obvious that this is true for the original graph. Also, you may want to rephrase your claims. Claim 1: If size of largest clique in a chordal decomposition of graph is say k then by tree decomposition we will get tree width at least k $\endgroup$ – user53923 Mar 24 '17 at 15:40
  • $\begingroup$ your question is valid but I think it follows from the definition of tree - width ( by chordal i.e. definition 1) so it is true for original graph or am I missing something ? and for second thing you mean to say $k -1$ or at least $k$ ( see the last paragraph en.wikipedia.org/wiki/Chordal_graph) $\endgroup$ – aaag Mar 24 '17 at 16:20
  • $\begingroup$ I think you are talking about this $tw(G) ≥ ω(G) − 1$ , but see in the claim 1 I am not saying largest clique in $G$, I am saying largest clique in chordal completion of $G$. $\endgroup$ – aaag Mar 24 '17 at 16:53
  • $\begingroup$ Ah no I was trying to say that if you take a tree decomposition of the chordal completion, you clearly have a bag of size k , but it could be less obvious for the original graph. (And yes I see I have missed that annoying -1 again... You are right) $\endgroup$ – user53923 Mar 24 '17 at 20:15
  • 1
    $\begingroup$ this is due the properties of chordal completion for original graph. $\endgroup$ – aaag Mar 27 '17 at 6:49
2
$\begingroup$

First, let me note that the claim, as stated in the question, is false: Consider the following graph:

$\begin{matrix} & & 2& - & 3\\ & \diagup\\ 1 & & | & & |\\ & \diagdown \\ & &4 &-& 5 \end{matrix} $

The complete graph on $5$ vertices is a chordal completion of this graph. However, this graph has treewidth $2$. (A decomposition is $\{1,2,4\}$, $\{2,3,4\}$, $\{3,4,5\}$ )


The correct claim is

The treewidth of $G$ of is the size of the largest clique $\omega(G) - 1$ in a chordal completion with the minimum largest clique of the graph $G$.

Now, a proof is as follows: if the treewidth of $G$ by tree decomposition is $k$, then every tree decomposition has a bag of size at least $k$. We use the concept of a separator graph from a paper by Parra and Scheffler, in particular the fact that every maximal clique in the separator graph of $G$ is a tree decomposition of $G$ (This can be seen by comparing the definition of tree decompositions with those in the paper)

Then, by Theorem 4.7$^*$ from the same paper, every minimal chordal completion of $G$ has all the bags of some tree decomposition as a clique. This means every minimal chordal completion of $G$ has a clique of size $k$, so the chordal completion method also gives a tree-width of $k$. $\square$


*: Paraphrased in our notation, Theorem 4.7 states:

A graph $H$ is a minimal chordal completion of $G$ if and only if $H$ is the graph $G$ with exactly the edges added such that all vertex sets in $\mathcal{S}$ are cliques. Here $\mathcal{S}$ is a maximal clique in the separator graph, which consists of minimal separators of $G$.

I attempted to find a proof using only elementary techniques, but I don't think an easy proof without any deeper theory would be easy to find.

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