Mình vừa up lên arxiv một paper mới có tiêu đề "Greedy spanners are optimal in doubling metrics". Paper này đang được submit vào SoCG 2018, một hội nghị hàng đầu về hình học tính toán. Bài này mình giới thiệu vắn tắt kết quả và bài toán.

Ở đây $d_S(x,y)$ và $d_G(x,y)$ lần lượt là khoảng cách ngắn nhất giữa $x$ và $y$ trong $G$ và $S$. Tất nhiên, phương trình $(1)$ cũng đồng nghĩa với tập đỉnh của $S$ cũng là tập đỉnh của $G$.

Trong bài này, ta gọi tắt $(1+\epsilon)$-spanner là spanner.

Greedy Spanners

Một spanner có thể tìm được sử dụng thuật toán tham lam.

Nếu để ý kĩ thì thuật toán GreedySpanner chỉ là mở rộng của thuật toán Kruskal tìm cây khung nhỏ nhất.

Chứng minh đồ thị đầu ra của thuật toán GreedySpanner thỏa mãn tính chất trong phương trình $(1)$ không khó lắm. Chi tiết coi như bài tập cho bạn đọc. Một câu hỏi không tầm thường về tính chất của $S$ là:

Tại sao lại so sánh trọng số của $S$ với cây khung nhỏ nhất? Đơn giản là vì cây khung nhỏ nhất là đồ thị con có trọng số nhỏ nhất kết nối tất cả các đỉnh của $G$ lại với nhau. Do đó, ít nhất $S$ cũng phải có trọng số lớn hơn $\mathrm{MST}$.

Nói chung, nếu đồ thị $G$ không có gì đặc biệt thì $S$ đôi khi là chính $G$. Hay nói cách khác, trong trường hợp xấu nhất $w(S) \geq n/2 \cdot w(\mathrm{MST})$. Bài tập cho bạn: tìm một đồ thị như vậy.

Tuy nhiên, câu hỏi này trở nên cực kì không tầm thường nếu $G$ có cấu trúc đặc biệt. Mình sẽ minh họa cho điểm này ngay dưới đây.

$G$ là $H$-minor-free: Mình sẽ không định nghĩa chi tiết khái niệm $H$-minor-free ở đây. Mình khuyến khích bạn đọc xem trong liên kết wikipedia hoặc một bài viết trước đây của mình. Một điểm quan trọng là lớp đồ thị này khái quát hóa đồ thị phẳng. Đây là một bài toán mình mất 3 năm để giải mà mới chỉ thành công mới đây thôi. Trong bài bào đó, mình và đồng tác giả chứng minh được rằng:

$w(S) \leq \frac{|V(H)|\sqrt{\log (|V(H)|)}}{\epsilon^3} \log \frac{1}{\epsilon} \cdot w(\mathrm{MST}) \qquad (2)$

Biểu thức không có đẹp đẽ gì, nhưng thông tin chính là $w(S)$ lớn hơn $w(\mathrm{MST})$ không quá hằng số lần (ở đây $H$ và $\epsilon$ đều là hằng số), không phụ thuộc vào kích thước của tập đỉnh của đồ thị.

$G$ là Euclidean: Cụ thể hơn, tập đỉnh của $G$ là tập $n$ điểm trong không gian Euclidean có $\lambda$ chiều và cạnh là đường thằng nối các điểm đó, và trọng số của cạnh chính là khoảng cách Eucidean giữa hai điểm ($\ell_2$-norm). Narasimhan và Smid [1] chứng minh rằng:

$w(S) \leq \epsilon^{-O(\lambda)} \cdot w(\mathrm{MST}) \qquad (3)$

Nói gọn lại thì $S$ cũng chỉ "nặng hơn" $\mathrm{MST}$ hằng số lần ($\lambda, \epsilon$ đều là hằng số). Tuy nhiên, chứng minh của Narasimhan và Smid dài 60 trang. Mình luôn cảm thấy chứng minh này dài hơn mức cần thiết.

Kết quả trong paper mới của bọn mình là một chứng minh tương tự cho một trường hợp tổng quát hóa của không gian Euclidean. Điểm chính là chứng minh mới của bọn mình, không những đúng cho trường hợp tổng quát hơn, mà còn ngắn hơn nhiều. Chỉ có 14 trang (đó là bao gồm cả hơn 1 trang references và vài trang râu ria chém gió các kiểu). Để giới thiệu kết quả thì cần thêm một số khái niệm.

Remark: Mình không dùng $d$ để kí hiệu số chiều của không gian Euclidean là vì $d$ sẽ được sử dụng dưới đây để kí hiệu khoảng cách.

Doubling metrics

Nói một cách dễ hiểu hơn, nếu mọi quả bóng có bán kinh $r$, với $r$ bất kì, đều được phủ bởi không quá $2^\lambda$ quả bóng có bán kính $r/2$ thì không gian metric $(X,d)$ được gọi là một doubling metric có chiều $\lambda$.

Tại sao ta lại quan tâm đến cái không gian này? Well, nếu bạn lấy một tập điểm hữu hạn bất kì $X$ trong không gian Euclidean có số chiều $\lambda$, và xây dựng một không gian metric rời rạc $(X,d)$ với hàm khoảng cách rời rạc $d(.,.)$ là khoảng cách Euclidean thì không gian này là một doubling metric có số chiều $O(\lambda)$. Do đó, có thể hiểu doubling metric là phiên bản rời rạc, nhưng lại tổng quát hóa không gian Euclidean.

Năm 2015, Gottlieb [2] chứng minh rằng, nếu $G$ biểu diễn một doubling metric có số chiều $\lambda$ thì:

$w(S) \leq \lambda^{\lambda} \epsilon^{-O(\lambda)} \cdot w(\mathrm{MST}) \qquad (6)$

Điều đó có nghĩa $w(S)$ cũng chỉ năng hơn hằng số lần so với $\mathrm{MST}$. Tuy nhiên, nếu nhìn kĩ thì bạn sẽ thấy một khoảng cách giữa vế phải của $(6)$ và vế phải của $(3)$.

Kết quả mới của bọn mình chính là thu hẹp hai khoảng cách đó lại.

 
Kĩ thuật chứng minh có gì mới? Thực ra chả có gì mới cả. Bọn mình chỉ sửa đổi một chút kĩ thuật chứng minh trong công trình trước đây mà thôi. Phần còn lại: hope for the best from SoCG 2018.

Tham khảo

[1] G. Narasimhan and M. Smid. Geometric Spanner Networks, chapter Geometric Analysis: The Leapfrog Property, pages 257–317. Cambridge University Press, 2007. doi:10.1017/CBO9780511546884.
[2] L. A. Gottlieb. A light metric spanner. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 759–772, 2015. doi:10.1109/FOCS.2015.5