1congNghe.Com: Phân rã cây và độ rộng cây

Thursday, July 19, 2012

Phân rã cây và độ rộng cây

1. Giới thiệu

Độ rộng cây (tree-width) là một khái niệm sâu sắc và có nhiều ứng dụng. Độ rộng cây và phân rã cây (tree decomposition) do Robertson và Seymour định nghĩa và phát triển trong công trình 20 bài báo lừng danh, dài hơn 500 trang, chứng minh định lý Graph Minor. Khái niệm này được họ giới thiệu năm 1983 trong bài số 2. Song song với họ và trước đó một chút, cũng có một vài tác giả định nghĩa các khái niệm tương tự hoặc gần giống với độ rộng cây, ví dụ như khái niệm cây- bán phần (partial {k} -tree) do Arnborg và Proskurowski phát triển (bài 1, 2), khái niệm số chiều đồ thị của Bertelè và Brioschi từ năm 1972, hay khái niệm hàm- {S} của đồ thị của Halin từ năm 1976. Xem thêm các bài của Bodlaender để biết thêm lịch sử.

Phân rã cây là một cách nhóm các đỉnh và cạnh của một đồ thị (hoặc một siêu đồ thị — hypergraph) thành một cây. (Xem định nghĩa dưới đây.) Cấu trúc của phân rã cây của một đồ thị {G} cho trước cho ta biết cấu trúc của {G} có gần với cấu trúc của một cây hay không. Độ rộng cây là một số đo xem đồ thị {G} có “gần” với một cây hay không. Nếu {G} gần với một cây, nghĩa là độ rộng cây của {G} nhỏ, thì có rất nhiều bài toán khó trên đồ thị tổng quát lại trở nên dễ với {G} vì ta có thể tận dụng cấu trúc của phân rã cây để xây dựng thuật toán.

Phân rã cây và độ rộng cây có rất nhiều ứng dụng: trong phân tích mạng xã hội, trong logic và độ phức tạp tính toán, trong cơ sở dữ liệu, trong probabilistic graphical models (đặc biệt là bài toán inference), trong VLSI design, xử lý ngôn ngữ tự nhiên, phân tích các ma trận thưa, vân vân. Phân rã cây và độ rộng cây cũng liên quan mật thiết đến đồ thị dây cung (chordal graphs), và tất nhiên là định lý graph minor. Rất nhiều bài toán NP-khó lại ở trong P khi giới hạn vào các đồ thị có độ rộng cây bị chặn. Một chương của quyển sách thuật toán của Kleinberg và Tardos nói về độ rộng cây và các thuật toán. Một tham khảo tốt về liên hệ giữa phân rã cây và đinh lý Graph Minor là chương 12 của quyển sách miễn phí của Diestel.

2. Định nghĩa và vài thuộc tính

Xét một đồ thị {G=(V,E)} cho trước. Phân rã cây của {G} là một cặp

$\displaystyle (\mathcal T = (T, E^{\mathcal T}), \{X_t \ | \ t \in T\})$

trong đó ${\mathcal T}$ là một cây với tập đỉnh {T} và tập cạnh ${E^{\mathcal T}}$ , và ${\{X_t\}_{t\in T}}$ là một bộ các tập con của {V} thoả mãn hai tính chất sau đây:

(a) Với mọi cạnh ${(u,v) \in E}$ , tồn tại một đỉnh cây ${t\in T}$ sao cho ${X_t}$ chứa cả lẫn
(b) Với mọi đỉnh ${v \in V}$ , tập ${\{ t \ | \ v \in X_t\}}$ khác rỗng và là tập đỉnh của một cây con của cây ${\mathcal T}$ . (Hoặc, một cách tương đương, ta có thể thay điều kiện này bằng điều kiện rằng với mọi bộ ba đỉnh cây ${t_1,t_2,t_3 \in T}$ , nếu ${t_2}$ nằm trên đường dẫn từ ${t_1}$ đến ${t_3}$ thì ${X_{t_1} \cap X_{t_3} \subseteq X_{t_2}}$ .)

Độ rộng của một phân rã cây là đại lượng ${\max_{t\in T} |X_t|-1}$ . Độ rộng cây của đồ thị {G} là độ rộng nhỏ nhất của một phân rã cây của {G} . Ta sẽ dùng ${\text{tw}(G)}$ để chỉ độ rộng cây của {G} . Hình sau minh hoạ phân rã cây.

Để phát triển một ít trực quan về khái niệm phân rã cây và độ rộng cây, hai bài tập sau đây khá đơn giản và bổ ích.

Exercise 1 Chứng minh rằng độ rộng cây của một cây là , và độ rộng cây của một chu trình (cycle) là .

Exercise 2 Gọi ${K\subseteq V}$ là một clique bất kỳ của , và ${(\mathcal T = (T, M), \{X_t \ | \ t \in T\})}$ là một phân rã cây bất kỳ. Chứng minh rằng có một đỉnh cây ${t\in T}$ sao cho ${K \subseteq X_t}$ . Từ đó suy ra, ${\text{tw}(G) \geq \omega(G) - 1}$ , trong đó ${\omega(G)}$ là số clique (clique number) của đồ thị .

Nếu đồ thị {G} là siêu đồ thị (hypergraph), ta cũng định nghĩa độ rộng cây y như trên, thay cạnh bằng siêu cạnh trong điều kiện (a) của định nghĩa.

3. Liên hệ với cây- bán phần và đồ thị dây cung

Để mô tả thêm một số thuộc tính khác của phân rã cây, ta nói thêm về liên hệ của nó với khái niệm cây- {k} bán phần (partial {k} -tree) và với lớp các đồ thị dây cung.

Một cây- ( {k} -tree) là một đồ thị được định nghĩa như sau. Một {k} -clique bất kỳ là một cây- {k} . Nếu {G} là một cây- {k} , gọi {K} là một {k} -clique bất kỳ trong {G} . Tạo một đỉnh mới {v} và nối nó với tất cả các đỉnh của {K} thì ta có một cây- {k} mới (lớn hơn {G} ). Định nghĩa đệ quy này cho ta hình dung được cách mà một cây- {k} có thể được xây dựng từng bước một. Cây- bán phần (partial {k} -tree) là một đồ thị con phủ (spanning subgraph) của một cây- {k} .

Năm 1987, Wimer và Scheffler chứng minh liên hệ sau đây.

Exercise 3 Đồ thị có độ rộng cây nhiều nhất là nếu và chỉ nếu là một cây- bán phần.

Cuối những năm 80 thế kỷ trước, có khá nhiều công trình cho thấy các bài toán NP-khó trên đồ thị bất kỳ thì lại trở nên dễ trên các cây- {k} bán phần. Dần già sự liên hệ giữa cây- {k} và phân rã cây trở nên rõ ràng hơn và có nhiều công trình khác dùng phân rã cây để thiết kế thuật toán hiệu quả cho các bài toán NP-khó dùng quy hoạch động. Để cảm nhận được tại sao các bài toán NP-khó lại dễ với lớp các đồ thị có độ rộng cây nhỏ (bị chặn bởi hằng số), ta xem tiếp liên hệ với các đồ thị dây cung.

Một đồ thị dây cung (chordal graph) là một đồ thị mà bất kỳ chu trình (cycle) nào với chiều dài {>3} của đồ thị cũng đều có một dây cung (chord — nghĩa là một cạnh nối hai đỉnh không kề nhau trên chu trình đó). Các đồ thị dây cung có nhiều thuộc tính rất thú vị. Ví dụ như một định lý cổ điển của nhà toán học quá cố Gabriel Dirac nói rằng một đồ thị là đồ thị dây cung nếu và chỉ nếu bất kỳ một minimal separator nào của đồ thị cũng là một clique. Từ đó ta có thể chứng minh rằng một cây- {k} là một đồ thị dây cung.

Bắt đầu từ một đồ thị {G} bất kỳ, nếu còn một chu trình dài hơn {3} mà không có dây cung, ta thêm vào dây cung tuỳ hỉ. Làm cho đến khi không thêm được dây cung nữa, thì rõ ràng là ta đạt được một đồ thị dây cung {H} chứa {G} . Đồ thị {H} được gọi một cách tự nhiên là đồ thị tam giác hoá (triangulation) của {G} .

Theorem 1 Gọi là đồ thị tam giác hoá của với độ rộng cây nhỏ nhất, hay nói cách khác là đồ thị dây cung chứa với độ rộng cây nhỏ nhất, thì độ rộng cây của bằng độ rộng cây của .

Với một đồ thị {G} bất kỳ và số {k} cho trước, câu hỏi xem độ rộng cây của {G} có nhỏ hơn hoặc bằng {k} hay không là bài toán NP-khó. Tìm đồ thị dây cung {H} chứa {G} với độ rộng cây nhỏ nhất cũng là bài toán NP-khó. Tuy nhiên, nếu ta biết {G} là đồ thị dây cung thì bài toán lại trở thành dễ.

Một ví dụ của đồ thị dây cung ta hay gặp trong thiết kế thuật toán là đồ thị quãng (interval graph), rất hay gặp trong các bài toán scheduling. Đồ thị quãng đơn giản nhất là đồ thị của một tập hữu hạn các khoảng đóng trên trục số thực. Mỗi khoảng đóng là một đỉnh của đồ thị và hai đỉnh nối nhau nếu hai khoảng này giao nhau. Trong scheduling thì mỗi khoảng có thể đại diện cho thời gian bắt đầu và kết thúc của một tác vụ. Schedule các tác vụ tương đương với tô màu các đỉnh của đồ thị quãng. Ta dùng một thuật toán tham lam miễn là các khoảng đóng được xếp theo một trật tự nhất định là có lời giải tối ưu. Điều này cũng đúng với các đồ thị dây cung nói chung: bài toán tô màu đồ thị là dễ đối với các đồ thị dây cung. Từ năm 1976 Rose-Lueker-Tarjan đã thiết kế thuật toán hiệu quả tìm thứ tự các đỉnh của một đồ thị dây cung sao cho tô màu tham lam thành tối ưu.

4. Thuật toán tìm phân rã cây

Bài toán tìm phân rã cây tối ưu (với độ rộng cây nhỏ nhất) là bài toán NP-khó. Tuy nhiên, nó lại giải được trong thời gian đa thức nếu đồ thị nhập là đồ thị dây cung.

Hồi 1984, Tarjan và Yannakakis thiết kế một thuật toán rất đơn giản để nhận diện một đồ thị dây cung trong thời gian tuyến tính. (Từ đó, ta có thể nhận diện xem một siêu đồ thị có phải là phi-chu-trình [acyclic] hay không; nhưng ta sẽ dùng kết quả này trong bài tới.) Biến thể nhỏ của thuật toán này cũng xây dựng được phân rã cây của đồ thì dây cung đã được nhận dạng.

Với một đồ thị tổng quát thì xây dựng một phân rã cây tối ưu là bài toán NP-khó. Tuy nhiên, bài toán này thuộc vào lớp fixed-parameter tractable (FPT — à ha! bây giờ các bạn đã biết FPT nghĩa là gì, không phải Food Processing Technologies nhé.) Cụ thể hơn, năm 1996 Bodlaender thiết kế một thuật toán tìm phân rã cây tối ưu của một đồ thị {G} cho trước trong thời gian ${O(2^{\text{poly}(\text{tw}(G))}|V(G)|)}$ . Kết quả này cũng đúng cho cả siêu đồ thị {H} . Đại khái, ta xây dựng cái gọi là đồ thị Gaifman của {H} rồi chạy thuật toán Bodlaender trên đồ thị Gaifman này. Dễ chứng minh rằng độ rộng cây của {H} và của đồ thị Gaifman của nó là bằng nhau.

Từ năm 1987, Arnborg-Corneil-Proskurowski đã thiết kế thuật toán cho bài này với thời gian chạy là ${O(|V(H)|^{\text{tw}(H)+2})}$ . Nếu siêu đồ thị {H} là nhỏ thì có thể thuật toán này tốt hơn của Bodleander.

Năm 95 thì Bodlaender và các đồng tác giả thiết kế thuật toán xấp xỉ độ rộng cây với tỉ lệ xấp xỉ ${O(\log n)}$ . Năm 2002, tỉ lệ này giảm xuống còn ${O(\log \text{tw}(G))}$ nhờ bài của Eyal Amir. Năm 2008, tỉ lệ này được Feige-Hajaghaji-Lee giảm xuống còn ${O(\sqrt{\log \text{tw}(G)})}$ . Một bài toán mở rất quan trọng là tìm thuật toán xấp xỉ độ rộng cây xuống trong tỉ lệ hằng số.

Link to full article

1congNghe.Com

Thursday, July 19, 2012

Phân rã cây và độ rộng cây

No comments:

Post a Comment

Popular Posts