## Tuesday, August 14, 2007

### Studying treewidth of a graph

A tree-decomposition of a graph G = (V, E) is a pair $(\{X_i\mid i\in I\}, T = (I, F))$ with $\{X_i \mid i\in I\}$ a family of subsets of V, one for each node of T, and T is a tree such that

• $\bigcup_{i\in I} X_i = V.$

• for all edges $(v, w)\in E$ , there exists an $i\in I$ with $v\in X_i$ and $w\in X_i$.
• for all $i, j, k\in I$, if j is on the path from i to k in T, then $X_i\cap X_k\subseteq X_j.$
• The treewidth of a tree-decomposition $(\{X_i\mid i\in I\}, T = (I, F))$ is $\mbox{max}_{i\in I}|X_i|-1.$ The treewidth of a graph G is the minimum treewidth over all possible tree-decompositions of G.

====================================================

感覺上，treewidth 好像是一個圖 G 中 最大 clique 之 size 減 1，不知道有沒有反例。另外，clique tree 是 tree-decomposition 的特例，只是多了一條限制：tree 上的每個 node 都是原圖 G 上的 maximal clique。

如果一個圖的 treewidth 為 bounded，那麼很多原本是 intractable 的 graph problems，就可以在 polynomial time (甚至很多可以在 linear time) 被解掉。譬如： Independent Set Problem, Hamiltonian Circuit Problem, Steiner tree problem 等等。

在 R. Niedermeier 的 Invitation to Fixed-Parameter Algorithms 一書中提到底下事實：
For constant k, there is a famous resulting giving a linear-time algorithm to compute whether a graph has treewidth at most k. More precisely, the algorithm has running time $2^{\Theta(k^3)}\cdot k^{O(1)} \cdot n.$
此外，給定一個 parameter k 與一個圖 G 當作 input，"決定 G 的 treewidth 是否至多為 k " 的問題已被證明為 NP-C [cite: ACP87]。但是，對於任一固定的 k，這問題存在一個 O(nlog n) 的演算法 [cite: R92]。

[ACP87] S. Arnborg, D. G. Corneil, and A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Math., Vol. 8 (1987), pp. 277-284.
[R92] B. Reed: Finding approximate separators and computing treewidth quickly. STOC'92, pp. 221-228.