vertex_cover.cpp

// vertex_cover.cpp
// -----------------------------------------------------------------
// Vertex Cover（頂點覆蓋）：
//   1. 精確解：k-分支限界（FPT，O(2^k · poly)）+ 求最小覆蓋
//   2. 2-近似：極大匹配的兩端點（保證 <= 2·OPT）
//   3. 度數啟發式（貪婪挑最大度）——無保證的對照組
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o vertex_cover vertex_cover.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

using Edges = vector<pair<int,int>>;

// ---------- 1. 精確：分支限界 ----------
// 觀察：任一條未覆蓋邊 (u,v)，答案必含 u 或 v -> 兩分支，深度 <= k
class VertexCoverExact {
public:
    long long nodes = 0;

    // 是否存在大小 <= k 的覆蓋；cover 傳回實際選點
    bool solveK(const Edges& edges, int n, int k, vector<int>& cover) {
        nodes = 0;
        vector<bool> chosen(n, false);
        bool ok = dfs(edges, chosen, k);
        cover.clear();
        for (int i = 0; i < n; ++i)
            if (chosen[i]) cover.push_back(i);
        return ok;
    }

    // 最小覆蓋：k 從 0 遞增
    vector<int> minimumCover(const Edges& edges, int n) {
        vector<int> cover;
        for (int k = 0; k <= n; ++k)
            if (solveK(edges, n, k, cover)) return cover;
        return cover;
    }
private:
    bool dfs(const Edges& edges, vector<bool>& chosen, int k) {
        ++nodes;
        // 找第一條未覆蓋的邊
        const pair<int,int>* uncovered = nullptr;
        for (const auto& e : edges)
            if (!chosen[e.first] && !chosen[e.second]) { uncovered = &e; break; }
        if (!uncovered) return true;                    // 全覆蓋
        if (k == 0) return false;                       // 配額用盡
        auto [u, v] = *uncovered;
        chosen[u] = true;                               // 分支 1：選 u
        if (dfs(edges, chosen, k - 1)) return true;
        chosen[u] = false;
        chosen[v] = true;                               // 分支 2：選 v
        if (dfs(edges, chosen, k - 1)) return true;
        chosen[v] = false;
        return false;
    }
};

// ---------- 2. 2-近似：極大匹配 ----------
vector<int> vertexCover2Approx(const Edges& edges, int n) {
    vector<bool> in(n, false);
    vector<int> cover;
    for (auto [u, v] : edges) {
        if (in[u] || in[v]) continue;
        in[u] = in[v] = true;                           // 兩端都拿
        cover.push_back(u);
        cover.push_back(v);
    }
    return cover;
}

// ---------- 3. 貪婪最大度（教學對照：無近似保證！） ----------
vector<int> vertexCoverGreedyDegree(Edges edges, int n) {
    vector<int> cover;
    while (true) {
        vector<int> deg(n, 0);
        for (auto [u, v] : edges) { ++deg[u]; ++deg[v]; }
        int best = max_element(deg.begin(), deg.end()) - deg.begin();
        if (deg[best] == 0) break;
        cover.push_back(best);
        Edges rest;
        for (auto& e : edges)
            if (e.first != best && e.second != best) rest.push_back(e);
        edges = std::move(rest);
    }
    return cover;
}

static bool verifyCover(const Edges& edges, const vector<int>& cover) {
    set<int> s(cover.begin(), cover.end());
    for (auto [u, v] : edges)
        if (!s.count(u) && !s.count(v)) return false;
    return true;
}

static void show(const string& tag, const vector<int>& cover, const Edges& e) {
    cout << tag << " size=" << cover.size() << "  {";
    for (size_t i = 0; i < cover.size(); ++i)
        cout << cover[i] << (i + 1 < cover.size() ? "," : "");
    cout << "}  valid=" << (verifyCover(e, cover) ? "yes" : "NO!") << "\n";
}

int main() {
    // ---- 範例 1：星星圖（貪婪==最優，近似=2x） ----
    cout << "=== Example 1: star graph K1,5 ===\n";
    Edges star = {{0,1},{0,2},{0,3},{0,4},{0,5}};
    VertexCoverExact ex;
    show("exact  ", ex.minimumCover(star, 6), star);
    show("2-apx  ", vertexCover2Approx(star, 6), star);
    show("greedy ", vertexCoverGreedyDegree(star, 6), star);
    cout << "\n";

    // ---- 範例 2：路徑 P6（近似的表現） ----
    cout << "=== Example 2: path P6 ===\n";
    Edges path = {{0,1},{1,2},{2,3},{3,4},{4,5}};
    show("exact  ", ex.minimumCover(path, 6), path);
    show("2-apx  ", vertexCover2Approx(path, 6), path);
    cout << "\n";

    // ---- 範例 3：Petersen 圖（OPT=6） ----
    cout << "=== Example 3: Petersen graph ===\n";
    Edges pet = {
        {0,1},{1,2},{2,3},{3,4},{4,0},
        {5,7},{7,9},{9,6},{6,8},{8,5},
        {0,5},{1,6},{2,7},{3,8},{4,9}};
    auto opt = ex.minimumCover(pet, 10);
    show("exact  ", opt, pet);
    cout << "  (branching nodes = " << ex.nodes << ")\n";
    show("2-apx  ", vertexCover2Approx(pet, 10), pet);
    show("greedy ", vertexCoverGreedyDegree(pet, 10), pet);
    cout << "\n";

    // ---- 範例 4：FPT 的意義——n 大但 k 小 ----
    cout << "=== Example 4: FPT — big n, small k ===\n";
    // 100 個頂點的稀疏圖：一條長鏈 + 幾條額外邊
    Edges big;
    for (int i = 0; i < 20; ++i) big.push_back({i, i + 1});
    big.push_back({30, 40});
    big.push_back({50, 60});
    big.push_back({70, 80});
    vector<int> cov;
    for (int k = 1; k <= 14; ++k) {
        if (ex.solveK(big, 100, k, cov)) {
            cout << "n=100, |E|=" << big.size()
                 << " -> minimum cover k=" << k
                 << " (nodes=" << ex.nodes << ")\n";
            break;
        }
    }
    cout << "Search depth bounded by k, not n -> FPT: O(2^k * poly(n))\n";
    return 0;
}