Trong bài trước, chúng ta đã tìm hiểu về NP-complete và 2 bài toán NP-complete đầu tiên là Sat và 3Sat. Công cụ để chứng minh một bài toán thuộc NP-complete là quy dẫn (reduction), mà cụ thể là Lemma 3 trong bài trước. Nói ngắn gọn, để chứng minh một bài toán $B$ thuộc NP-complete, ta sẽ:
- Chứng minh $B \in $ NP. Bước này thường không khó, do đó, trong bài viết mình sẽ bỏ qua bước này. Có một số bài toán mà chứng minh bước này trở nên không tầm thường. Tuy nhiên, chúng ta sẽ không xét những bài toán đó ở đây. Bạn có thể xem một số ví dụ chứng minh tại đây.
- Lấy một bài toán $A$ mà ta đã biết thuộc NP-complete và chứng minh rằng $A \preceq_{\mathrm{Karp}} B$. Chọn bài toán $A$ nào để quy về $B$ là một vấn đề kĩ thuật rất khó có thể mô tả. Thông thường ta chọn các bài toán có chùng tính chất nào đó. Ví dụ quy các bài toán trên đồ thị về các bài toán trên đồ thị. Hiện tại ta mới chỉ có 2 bài toán Np-complete trong tay là Sat và 3Sat. Về sau, khi ta càng chứng minh nhiều bài toán Np-complete thì ta càng có nhiều lựa chọn cho bài toán $A$.
Remark: Các bạn phải đặc biệt chú ý chiều của quy dẫn:: $A \preceq_{\mathrm{Karp}} B$ nếu ta muốn sử dụng bài toán $A$ để chứng minh bài toán $B \in$ NP-complete. Càng về sau chúng ta càng dễ nhầm chiều.
Trong post này, chúng ta tập trung vào một số bài toán NP-complete trên đồ thị: Tập độc lập (indepndent set), phủ đỉnh (vertex cover), clique, chu trình Hamilton và bài toán người du lịch (tsp). Chúng ta sẽ thực hiên quy dẫn theo Figure 1.
Figure 1:Quy dẫn giữa một số bài toán trong đồ thị.
Quy dẫn từ Sat sang 3Sat ta đã trình bày trong bài trước. Chúng ta sẽ bỏ qua quy dẫn từ 3Sat về HalmintonianCycle vì quy dẫn khá phức tạp, khó trình bày trong khuôn khổ cho phép của post này. Các bạn có thể xem thêm tại [1] và CLRS [2]. Các quy dẫn khác trong hình ta sẽ trình bày ở post này.
Trước khi đi vào quy dẫn, mình muốn làm rõ một vài khái niệm và kí hiệu với bài toán 3Sat. Bạn đọc cần phân biệt biến (variables) và literals. Mỗi biến $x_i$ có 2 literals tương ứng là $x_i$ và phủ của nó $\bar{x}_i$. Nếu $x_i$ được gán giá trị False thì literal $x_i$ sẽ có giá trị False còn literal $\bar{x}_i$ sẽ có giá trị True. Một mệnh đề (clause) của 3Sat có giá trị True khi và chỉ khi ít nhất 1 literal trong mệnh đề đó có giá trị True, mặc dù tất cả các biến trong mệnh đề đó có thể nhận giá trị False.
Ngoài ra, theo định nghĩa chuẩn của 3Sat, mỗi mệnh đề của 3Sat có không quá 3 literals. Thực tế, bài toán 3SAT với mỗi mệnh đề có đúng 3 literals cũng là NP-complete. Do đó, ta sẽ giả sử mỗi mệnh đề của 3Sat có đúng 3 literals, để ta không phải xét các trường hợp khi thực hiện quy dẫn.
Bài toán tập độc lập
Ta bắt đầu với bài toán tập độc lập (independent set), do quy dẫn từ 3SAT về tập độc lập là quy dẫn phức tạp nhất của bài viết. Sau khi thực hiện quy dẫn này rồi, các quy dẫn khác sẽ dễ hơn nhiều.
Một tập đỉnh được gọi là một tập độc lập của một đồ thị nếu như không có cạnh nào nối hai đỉnh cùng thuộc một tập đó (xem lại chi tiết định nghĩa và ví dụ tại đây).
Ta sẽ chứng minh:
Chứng minh: Ta sẽ quy dẫn bài toán 3Sat về IndependentSet như sau: bắt đầu từ một biểu thức $\varphi(n,m)$ thuộc bài toán 3Sat, ta sẽ xây dựng một đồ thị $G(V,E)$ và một số nguyên $K$ (trong thời gian đa thức) sao cho $\varphi(n,m)$ có một phép gán có giá trị True khi và chỉ khi đồ thị $G(V,E)$ có một tập độc lập với kích thước ít nhất $K$.
Ta bắt đầu bằng cách xây dựng các gadget cho từng mệnh đề của $\varphi(n,m)$. Sau đó chúng ta sẽ tìm cách nối các gadget lại với nhau. Một gadget ở đây được hiểu là một đồ thị con để phục vụ cho mục đích giải bài toán của chúng ta. Dựa trên định nghĩa, ta có nhận xét: với mỗi cạnh $u,v$, tối đa một đỉnh thuộc tập độc lập.
Gadget mệnh đề: với mỗi mệnh đề có 3 biến, ví dụ $C = (x \vee \bar{y} \vee z)$, ta tạo ra 3 đỉnh mới có nhãn tương ứng $x, \bar{y}$ và $z$. Sau đó, ta nối 3 đỉnh này đôi một với nhau. Xem Figure 2. Chú ý, dấu phủ trên biến $y$ không có gì đặc biệt, chỉ để minh họa một mệnh đề có cả biến và phủ của biến. Các mệnh đề không có phủ hoặc chỉ có phủ ta làm tương tự. Nhận thấy, với mỗi gadget mệnh đề, chỉ có tối đa một đỉnh thuộc tập độc lập, và đỉnh nào thuộc tập độc lập thì literal tương ứng sẽ nhận giá trị True. Ta sẽ thiết lập giá trị $K$ sao cho đúng một trong 3 đỉnh của gadget mệnh đề sẽ thuộc tập độc lập.
Figure 2: Gadget cho mệnh đề $x \vee \bar{y} \vee z$.
Giờ ta sẽ nối các gadget mệnh đề lại với nhau. Hiện tại, số đỉnh của đồ thị là $ 3m$ vì với mỗi mệnh đề ta có 3 đỉnh. Với mỗi biến $x_i$, chỉ có đúng một trong hai literals $x_i$ và $\bar{x}_i$ nhận giá trị True, do đó, ta sẽ nối mọi cặp đỉnh có nhãn dạng $x_i$ và $\bar{x}_i$ lại với nhau. Do đó, chỉ đúng có một trong hai đỉnh $x_i$ và $\bar{x}_i$ thuộc tập độc lập. Đỉnh nào thuộc tập độc lập thì ta thiết lập literal tương ứng sẽ nhận giá trị True.
Như vậy ta đã hoàn thành đồ thị. Xem minh họa trong Figure 3. Để thiết lập giá trị $K$, ta thấy $\varphi(n,m)$ nhận giá trị True khi và chỉ khi tồn tại một cách gán biến sao cho mọi mệnh đề có giá trị True. Hay nói cách khác, mỗi mệnh đề đều có một literal True. Điều đó có nghĩa, mỗi gadget mệnh đề có ít nhất 1 biến thuộc tập độc lập. Do đó, ta thiết lập $K = m$.
Figure 3: Các cạnh màu đỏ gạch là các cạnh nối giữa các gadget mệnh đề.
Giờ ta sẽ chứng minh $\varphi(n,m)$ có một phép gán có giá trị True khi và chỉ khi đồ thị $G(V,E)$ có một tập độc lập với kích thước ít nhất $m$.
Chiều thuận $(\Rightarrow)$: Với mỗi biến $x_i$, nếu phép gán của $\varphi(n,m)$ gán cho $x_i$ giá trị True, ta lấy đỉnh có nhãn $x_i$ của mỗi mệnh đề vào tập $X$. Ngược lại, ta lấy đỉnh có nhãn $\bar{x}_i$ vào tập $X$. Do phép gán đó là phép gán True, mỗi mệnh đề đều có ít nhất một literal có giá trị True. Nếu mệnh đề có ít nhất 2 literals có giá trị có ít nhất một literal có giá trị , ta cũng chỉ lấy đúng 1 đỉnh trong số ít nhất 2 đỉnh tương ứng để đảm bảo $X$ là tập đọc lập. Do đó, $X$ có đúng (do đó, ít nhất) $m$ đỉnh.
Chiều ngược $(\Leftarrow)$: Gọi $X$ là một tập độc lập có kích thước ít nhất $m$ trong đồ thị. Do đồ thị có $3m$ đỉnh và mỗi gadget mệnh đề chỉ có tối đa $1$ đỉnh trong $X$, ta suy ra $X$ có đúng $m$ đỉnh. Trong $X$ không có 2 đỉnh nào có dạng $x_i$ và $\bar{x}_i$ với mọi $i$ vì theo cách xây dựng đồ thị, ta sẽ có một cạnh nối 2 đỉnh đó. Do đó, trong $X$ có đúng $m$ literals, và các literals tương ứng với mỗi biến $i$ chỉ có dạng $x_i$ hoặc $\bar{x}_i$. Giờ ta sẽ gán giá trị cho biến sao cho mọi literals trong $X$ đều nhận giá trị True. Do $X$ chứa đúng một literal cho mỗi clause, cách gán này khiến mọi mệnh đề có giá trị True, do đó, biểu thức sẽ có giá trị True (dpcm).
Phủ đỉnh và Clique
Cho một đồ thị $G(V,E)$, một tập đỉnh $X\subseteq V$ được gọi là một tập phủ đỉnh (vertex cover) nếu như với mọi cạnh $e$ của đồ thị, ít nhất một trong hai đầu mút của nó thuộc $X$. Tập $X$ được gọi là một Clique nếu như giữa mọi cặp đỉnh của $X$ đều tồn tại một cạnh của đồ thị nối hai đỉnh đó. Xem ví dụ trong hình minh họa trong Figure 4.
Figure 4: (a) Các đỉnh được tô đậm màu đỏ thuộc Clique có kích thước 4 trong đồ thị và (b) các đỉnh được tô đậm màu xanh là một tập phủ đỉnh của đồ thị.
Bài toán VertexCover được định nghĩa như sau:
Ta có:
Chứng minh: Ta sẽ quy dẫn từ bài toán IndependentSet. Ở đây mình chỉ lượt qua ý tưởng. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc. Chứng minh dựa trên nhận xét: nếu $X$ là một tập phủ đỉnh của đồ thị thì $V\setminus X$ là một tập độc lập của đồ thị. Nhận xét này có thể chứng minh bằng phản chứng như sau. Kí hiệu $\bar{X} = V\setminus X$. Nếu $\bar{X}$ không phải là tập độc lập thì sẽ tồn tại một cạnh nối hai đỉnh của $u,v$ của $\bar{X}$. Theo định nghĩa của phủ đỉnh, ít nhất một trong hai đầu mút của cạnh này phải thuộc tập phủ đỉnh, ta thu được phản chứng.
Bài toán Clique được định nghĩa như sau:
Ta có:
Chứng minh: Ta sẽ quy dẫn từ bài toán IndependentSet. Cũng như Lemma 2, mình chỉ nêu ý tưởng chính. Chi tiết chứng minh theo từng bước coi như bài tập của bạn đọc.
Ta định nghĩa đồ thị bù, kí hiệu $\bar{G}(\bar{V}, \bar{E})$, của đồ thị $G(V,E)$ như sau. Tập đỉnh của đồ thị bù cũng là tập đỉnh của đồ thị gốc, i.e, $\bar{V} = V$. Tập cạnh của đồ thị bù là phần bù của tập cạnh của đồ thị gốc. Nói cách khác, nếu giữa hai đỉnh $u,v$ của đồ thị gốc không có cạnh nào nối chúng thì ta sẽ thêm cạnh $uv$ vào đồ thị bù và ngược lại.
Quy dẫn từ IndependentSet dựa trên nhận xét: $X$ là một Clique của đồ thị $G(V,E)$ khi và chỉ khi nó là một tập độc lập của đồ thị bù $\bar{G}(\bar{V}, \bar{E})$.
Chu trình Hamilton và bài toán người du lịch
Bài toán chu trình Hamilton và bài toán người du lịch (tsp) mình đã đã định nghĩa chi tiết kèm ví dụ ở post trước. Mình nhắc lại ngắn gọn hai bài toàn này tại đây.
Ta có:
Chứng minh: Như đã nói ở đầu bài viết, quy dẫn cho Hamiltonian cycle khá phức tạp và mình sẽ không trình bày cụ thể ở đây. Bạn đọc xem chứng minh chi tiết thêm tại note của Jeff Erickson [2]. Ta sẽ công nhận HamiltonianCycle là bài toán thuộc lớp Np-complete. Ta sẽ chứng minh Tsp $\in$ Np-complete bằng cách quy dẫn từ bài toán HamiltonianCycle.
Gọi $G(V,E)$ là đồ thị đầu vào của bài toán HamiltonianCycle. Ta quy đồ thị này thành đầu vào của bài toán Tsp bằng cách gán cho mỗi cạnh trọng số $1$ và thiết lập $K = n$. Ta có nhận xét: đồ thị $G(V,E)$ với các cạnh trọng số $1$ có một đường đi đóng có tổng trọng số nhỏ hơn hoặc bằng $n$ khi và chỉ khi mọi đỉnh xuất hiện đúng 1 lần trên đường đi, ngoại trừ đỉnh đầu và đỉnh cuối. Do đó, đường đi đóng là chính là một chu trình Hamilton của đồ thị $G(V,E)$.
Tham khảo
[1] J. Erickson. Lecture Notes on NP-hardness. UIUC. 2014
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (2nd ed.). Chapter 36. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. (2001).
[3] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of Np-Completeness. W. H. Freeman & Co., New York, NY, USA. 1979.
Recent Comments