Polynomial algorithms for graphs with bounded parameter-tree-width
by
Guantao Chen
Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303
Coauthors: Xue Wang, Department of Computer Science, Georgia State University, Atlanta, GA 30303

For a finite graph G, a sequence X₁, X₂, ..., X_p of subsets of V(G) is a path-decomposition of G if (a) for every edge e, some X_i contains both ends of e, and (b) for 1 ≤ i ≤ i' ≤ i" ≤ r, X_i∩X_i" ⊆ X_i'. The path-width of G is the minimum value of k ≥ 0 such that G has a path decomposition X₁, X₂, ..., X_p with |X_i| ≤ k+1. For each constant k and all graphs with path-width no more than k, Robertson and Seymour showed there are polynomial algorithms to find independence number, dominating number, and connected dominating number, respectively. Let r be a graph parameter. The r-path-width of G is the minimum value of k ≥ 0 such that G has a path decomposition X₁, X₂, ..., X_p such that r(G[X_i]) ≤ k+1. We showed that, for every k and all graphs of the r-path-width no more than k, there are polynomial algorithms to find independence number, dominating number, and connected-dominating number, where r is the corresponding parameter. Using this result, we establish an approximation polynomial algorithm to find minimum connected dominating set for ad-hoc connected networks.

Robertson and Seymour extended their results to graphs with bounded tree-width. We extend our result to graphs with bounded tree-width for trees with bounded-degree.

Date received: February 26, 2008