Tuesday, August 14, 2007

Studying treewidth of a graph

A tree-decomposition of a graph G = (V, E) is a pair with a family of subsets of V, one for each node of T, and T is a tree such that

  • for all edges , there exists an with and .
  • for all , if j is on the path from i to k in T, then
  • The treewidth of a tree-decomposition is 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
    此外,給定一個 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.

    No comments: