Một số bài toán NP-complete trên đồ thị -- NP-complete problems on graphs

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 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ẽ:

  1. 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.
  2. 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 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.

graph-reduction
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 3Satkhô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).

IndependentSet. Cho một đồ thị vô hướng G(V,E) và một số nguyên K. Xác định xem đồ thị đó có một tập độc lập kích thước ít nhất K hay không?

 
Ta sẽ chứng minh:

Lemma 1: IndependentSet  \in Np-complete

 
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}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.
clause-gadget
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\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\bar{x}_i lại với nhau. Do đó, chỉ đúng có một trong hai đỉnh x_i\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.

complete-reduction
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đúng m đỉnh. Trong X không có 2 đỉnh nào có dạng x_i\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.

vertex-cover
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:

VertexCover. Cho một đồ thị vô hướng G(V,E) và một số nguyên K. Có tồn tại hay không một tập phủ đỉnh có kích thước không quá K trong đồ thị?

 
Ta có:

Lemma 2: VertexCover  \in Np-complete

 
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:

Clique. Cho một đồ thị vô hướng G(V,E) và một số nguyên K. Có tồn tại hay không một Clique có kích thước không quá K trong đồ thị?

 
Ta có:

Lemma 3: Clique  \in Np-complete

 
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.

HamiltonianCycle. Cho một đồ thị vô hướng G(V,E). Một chu trình C trong đồ thị được gọi là chu trình Hamilton nếu chu trình này đi qua mỗi đỉnh đúng một lần. Xác định xem có tồn tại một chu trình Hamilton trong G(V,E) hay không?

 

Tsp. Cho một đồ thị vô hướng G(V,E), trong đó mỗi cạnh e\in E có một trọng số không âm w(e), và một số nguyên K. Một đường đi đóng (closed walk) là dãy đỉnh \{v_1,v_2,\ldots, v_\ell-1, v_\ell = v_1\} trong đó tồn tại một cạnh của đồ thị nối hai đỉnh liên tiếp v_i,v_{i+1} với mọi  1\leq i \leq i-1. Có tồn tại hay không một đường đi đóng (closed walk) trong G đi qua tất cả các đỉnh mà có tổng trọng số các cạnh trên đường đi không quá K?

 

Ta có:

Lemma 4: HamiltonianCycle Tsp là các bài toán Np-complete.

 
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.

Facebook Comments

Tags: , , , , , ,

Reply

Your email address will not be published. Required fields are marked *