Vertex Cover Problem บน Binary Tree

Vertex Cover ของกราฟ = Subset ของโหนด ที่ทุก Edge (u,v) มี **อย่างน้อยหนึ่งโหนด** อยู่ใน Subset

บน Binary Tree สามารถแก้ด้วย DP on Tree ได้อย่างมีประสิทธิภาพ

ตัวอย่าง Input และ Output

Binary Tree:
        20
       /  \
      8    22
     / \    \
    4  12    25
      / \
     10 14

Output: Minimal vertex cover: 3
Vertex Cover: {20, 12, 22} หรือ {8, 22, 12} เป็นต้น

อัลกอริทึม DP on Tree (Memoization)

ฟังก์ชัน vertexCover(root)

แนวคิด: 2 กรณีสำหรับแต่ละโหนด

1. Include Root: Root อยู่ใน Vertex Cover → Edge ระหว่าง Root และลูกทั้งสองถูกครอบคลุมแล้ว → ต้องการ Vertex Cover ของ Left Subtree + Right Subtree + 1 (สำหรับ Root)
2. Exclude Root: Root ไม่อยู่ใน Vertex Cover → **ลูกทั้งสองต้องอยู่ใน Vertex Cover** (เพื่อครอบคลุม Edge Root-Child) → ต้องการ Vertex Cover ของ Grandchildren ทั้ง 4 ตัว + 2 (สำหรับลูก 2 ตัว)

เลือกค่าน้อยกว่า (Minimum Vertex Cover)

Recurrence:

sizeWithRoot = 1 + VC(left) + VC(right)
sizeWithoutRoot = 0
if (left exists)  sizeWithoutRoot += 1 + VC(left->left) + VC(left->right)
if (right exists) sizeWithoutRoot += 1 + VC(right->left) + VC(right->right)

VC(root) = min(sizeWithRoot, sizeWithoutRoot)

ขั้นตอน (Memoization):

1. ถ้า root = NULL → 0
2. ถ้า Leaf (ไม่มีลูก) → 0 (ไม่มี Edge ต้องครอบคลุม)
3. ถ้า vCover != 0 → คืนค่าทันที
4. คำนวณ sizeWithRoot และ sizeWithoutRoot
5. root->vCover = min(sizeWithRoot, sizeWithoutRoot)
6. คืน root->vCover

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int data;
    int vCover;
    node *left, *right;
};

node* getNode(int data) {
    node* newNode = new node;
    newNode->data = data;
    newNode->vCover = 0;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int vertexCover(node* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 0;
    if (root->vCover != 0) return root->vCover;

    int sizeWithRoot = 1 + vertexCover(root->left) + vertexCover(root->right);
    int sizeWithoutRoot = 0;

    if (root->left)
        sizeWithoutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
    if (root->right)
        sizeWithoutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);

    root->vCover = min(sizeWithRoot, sizeWithoutRoot);
    return root->vCover;
}

int main() {
    node* root = getNode(20);
    root->left = getNode(8); root->right = getNode(22);
    root->left->left = getNode(4); root->left->right = getNode(12);
    root->left->right->left = getNode(10); root->left->right->right = getNode(14);
    root->right->right = getNode(25);

    cout << "Minimal vertex cover: " << vertexCover(root);
    return 0;
}

Output

Minimal vertex cover: 3

ความซับซ้อน

• Time: O(n) - แต่ละโหนดคำนวณ 1 ครั้ง
• Space: O(n) - Recursion stack + memoization

ขยายสู่ General Graph

Vertex Cover บน General Graph เป็น **NP-Complete** แต่บน Tree (และ Bipartite Graph) แก้ได้ด้วย DP/Polynomial Time

ความสัมพันธ์กับ Independent Set

บน Graph ใดๆ: Vertex Cover + Maximum Independent Set = |V| (Complement ของ Vertex Cover คือ Independent Set)