Thuật toán thiết lập độc lập tối đa

Question

Tôi không tin rằng tồn tại một thuật toán để tìm đỉnh độc lập tối đa được đặt trong biểu đồ lưỡng cực ngoài phương pháp bạo lực tìm tối đa trong số tất cả các tập độc lập có thể có.

Tôi tự hỏi về mã giả để tìm tất cả các tập đỉnh có thể có.

Nói cho một biểu đồ hai chân với 4 đỉnh màu xanh lam và 4 màu đỏ. Hiện nay tôi sẽ

Start with an arbitrary blue, 
    find all red that don't match this blue 
    put all these red in Independent Set 
    find all blue that dont match these red 
    put these blue in Independent Set 
    Repeat for next vertex in blue 

Repeat all over again for all blue then all vertices in red. 

Tôi hiểu rằng cách này không cung cấp cho tôi tất cả kết hợp Set độc lập càng tốt ở tất cả, kể từ sau khi bước đầu tiên tôi chọn toàn bộ các đỉnh màu bên cạnh đó không phù hợp chứ không phải là bước qua mọi khả năng.

Ví dụ được đưa ra một đồ thị với phù hợp với

B R 
1 1 
1 3 
2 1 
2 3 
3 1 
3 3 
4 2 
4 4 

Start with blue 1 
    Choose red 2 and 4 since they dont match 
    Add 2, 4 to independent Set 
    Choose 2 and 3 from blue since they dont with 2 or 4 from red 
    Add 2 and 3 from blue to independent set as well. 
Independent Set = 1,2,3 from blue 2,4 from red 
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set) 

Có cách nào tôi có thể cải thiện thuật toán này để tìm kiếm tốt hơn cho tất cả các khả năng. Tôi biết rằng một | Maximum Set cho một đồ thị hai mặt | = | Đỏ | + | Màu xanh | - | Kết hợp tối đa |.

Vấn đề nảy sinh với khả năng bằng cách chọn tất cả màu đỏ có thể trong lần đầu tiên cho một màu xanh cụ thể, nếu những màu đỏ đó kết nối với tất cả các màu xanh khác thì bộ của tôi chỉ có 1 màu xanh và đỏ.

Answer 1

Tôi không tin rằng tồn tại một thuật toán để tìm đỉnh độc lập tối đa được đặt trong biểu đồ lưỡng cực ngoài phương pháp bạo lực tìm tối đa trong số tất cả các tập hợp độc lập có thể có.

Có: tìm các thiết lập độc lập tối đa tương đương với việc tìm kiếm bìa đỉnh tối thiểu (bằng cách tham gia bổ sung của kết quả), và Konig's theorem khẳng định rằng cover đỉnh tối thiểu trong đồ thị hai phía tương đương với hợp tối đa, và rằng có thể được tìm thấy trong thời gian đa thức. Tôi không biết về việc tìm kiếm tất cả các trận đấu, nhưng có vẻ như có thể có nhiều người theo cấp số nhân.

Answer 2

Khi Aaron McDaid đề cập đến câu trả lời đã bị xóa của mình, vấn đề tìm một tập hợp độc lập tối đa tương đương với việc tìm kiếm một bản sao tối đa. Sự tương đương là việc tìm kiếm một tập độc lập tối đa trong biểu đồ G cũng giống như việc tìm kiếm một clique tối đa trong phần bổ sung của G. Vấn đề được biết là NP-complete.

Giải pháp bạo lực bạn đề cập đến mất O(n^2 2^n), nhưng bạn có thể làm tốt hơn điều này. Robson có một bài báo mang tên "" Thuật toán cho các bộ độc lập tối đa "từ năm 1986 cho một thuật toán mất O(2^{c*n}) cho hằng số 0<c<1 (Tôi tin rằng c là khoảng 1/4, nhưng tôi có thể nhầm lẫn). .

một điều cần lưu ý nếu bạn có một đồ thị hai phía là hai bên tạo thành một bộ độc lập. trong hoàn chỉnh song phương graph K_{b,r} mà được phân chia B x R với |B|=b và |R|=r nơi có một cạnh từ mỗi đỉnh trong B cho mọi đỉnh trong R và không có trong phạm vi B cũng không có gì trong phạm vi R, một bộ độc lập tối đa là B nếu b>=r, nếu không thì R.

Lấy B hoặc R sẽ không hoạt động nói chung.sdcvvc lưu ý ví dụ với các đỉnh {1,2,3,A,B,C} và cạnh {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. Trong trường hợp này, tập hợp độc lập tối đa là {1,2,B,C}, lớn hơn một trong hai phân vùng {A,B,C} hoặc {1,2,3}.

Nó có thể cải thiện thuật toán của Robson để bắt đầu với lớn hơn B hoặc R và tiếp tục từ đó, mặc dù tôi không chắc chắn sẽ tạo ra sự khác biệt bao nhiêu.

Hoặc, bạn có thể sử dụng Hopcroft–Karp algorithm trên phần bổ sung lưỡng cực của biểu đồ để tìm đối sánh tối đa và sau đó lấy các đỉnh được sử dụng trong kết hợp làm bộ độc lập. Điều này cho phép một thuật toán thời gian đa thức để giải quyết vấn đề.