Tìm vertex cover tối thiểu của đồ thị bằng nhị phân C++

Vertex Cover – Tập đỉnh sao cho mọi cạnh đều có ít nhất 1 đầu thuộc tập đó. Minimum Vertex Cover (MVC) – Vertex cover có kích thước nhỏ nhất.

Bài toán NP-hard trên đồ thị tổng quát. Đồ thị nhỏ (V ≤ 20-25) có thể dùng bitmask + binary search.

Thuật toán

• Kiểm tra tồn tại vertex cover kích thước k: duyệt mọi tập con k đỉnh (bitmask), kiểm tra bao phủ hết cạnh.
• Binary search trên k từ 1 đến V.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 20;
bool adj[MAXV][MAXV];

bool hasCover(int V, int k, int E) {
    int mask = (1 << k) - 1; // k bit 1 đầu tiên
    int limit = 1 << V;
    
    while (mask < limit) {
        bool covered[MAXV][MAXV] = {};
        int cnt = 0;
        
        for (int i = 0, v = 0; i < limit; i <<= 1, v++) {
            if (mask & i) {
                for (int u = 0; u < V; u++) {
                    if (adj[v][u] && !covered[v][u]) {
                        covered[v][u] = covered[u][v] = true;
                        cnt++;
                    }
                }
            }
        }
        if (cnt == E) return true;
        
        // Next combination (Gosper's hack)
        int c = mask & -mask;
        int r = mask + c;
        mask = (((r ^ mask) >> 2) / c) | r;
    }
    return false;
}

int minVertexCover(int V, int E) {
    int lo = 1, hi = V;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (hasCover(V, mid, E)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    memset(adj, 0, sizeof(adj));
    int V = 6, E = 5;
    auto add = [&](int u, int v) { adj[u][v] = adj[v][u] = 1; };
    add(2,3); add(2,4); add(3,5); add(4,5); add(4,6);
    // Đỉnh 1-indexed trong ví dụ, chuyển về 0-indexed
    // Thực tế cần điều chỉnh code cho 1-indexed hoặc 0-indexed
    cout << "Kich thuoc MVC: " << minVertexCover(V, E) << "\n";
    return 0;
}

Kết quả

Kich thuoc MVC: 2

Lưu ý: Code mẫu dùng 0-indexed. Đồ thị ví dụ: đỉnh {3,4} (1-indexed) bao phủ 5 cạnh.