C++ 이진 탐색으로 그래프의 최소 정점 커버 크기 구하기

개요

이 글에서는 이진 탐색(binary search)을 활용하여 주어진 그래프의 최소 정점 커버(minimum vertex cover) 크기를 구하는 C++ 프로그램을 살펴보겠습니다.

최소 정점 커버란 그래프의 모든 간선이 해당 집합에 포함된 정점 중 적어도 하나와 연결(인접)되도록 만드는 정점들의 집합입니다. 쉽게 말해, 그래프의 모든 간선을 '덮을' 수 있는 가장 작은 크기의 정점 집합이라고 할 수 있습니다.

예를 들어 다음과 같은 그래프가 있다고 가정해 보겠습니다.

2 ---- 4 ---- 6
|      |
|      |
|      |
3 ---- 5

이 그래프의 최소 정점 커버는 정점 3과 4입니다. 그래프의 모든 간선은 정점 3 또는 4에 인접해 있으므로, 단 두 개의 정점만으로 전체 간선을 모두 덮을 수 있습니다.

알고리즘 접근 방식

이 문제는 비트마스킹(bitmasking)과 이진 탐색을 조합하여 효율적으로 해결할 수 있습니다.

• check_cover 함수: k개의 정점을 선택하는 모든 조합을 비트마스크로 생성한 뒤, 각 조합이 그래프의 모든 간선을 커버하는지 검사합니다.
• find_cover 함수: 이진 탐색을 통해 정점 개수 범위 내에서 최소 커버 크기가 되는 k값을 빠르게 찾아냅니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
#define max 15
//그래프를 저장하는 배열
bool arr[max][max];
//최소 정점 커버가 존재하는지 확인
bool check_cover(int V, int k, int E) {
    int set = (1 << k) - 1;
    int limit = (1 << V);
    //'k' 크기의 간선을 표시하기 위한 배열
    bool vis[max][max];
    while (set < limit) {
        //반복마다 정점 커버 초기화
        memset(vis, 0, sizeof vis);
        int count = 0;
        //상위 비트 값 검사
        for (int j = 1, v = 1 ; j < limit ; j = j << 1, v++) {
            if (set & j) {
                //방문한 간선 표시
                for (int k = 1 ; k <= V ; k++) {
                    if (arr[v][k] && !vis[v][k]) {
                        vis[v][k] = 1;
                        vis[k][v] = 1;
                        count++;
                    }
                }
            }
        }
        //모든 간선이 커버된 경우
        if (count == E)
            return true;
        int c = set & -set;
        int r = set + c;
        set = (((r^set) >> 2) / c) | r;
    }
    return false;
}
//최소 정점 커버 찾기
int find_cover(int n, int m) {
    //이진 탐색 수행
    int left = 1, right = n;
    while (right > left){
        int mid = (left + right) >> 1;
        if (check_cover(n, mid, m) == false)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}
//그래프에 간선 삽입
void add_edge(int u, int v) {
    arr[u][v] = 1;
    arr[v][u] = 1;
}
int main() {
    memset(arr, 0, sizeof arr);
    int V = 6, E = 5;
    add_edge(2, 3);
    add_edge(2, 4);
    add_edge(3, 5);
    add_edge(4, 5);
    add_edge(4, 6);
    cout << "Size of Minimum Vertex Cover : " << find_cover(V, E) << endl;
    return 0;
}

실행 결과

Size of Minimum Vertex Cover : 2

실행 결과를 보면, 위에서 살펴본 그래프의 최소 정점 커버 크기는 2임을 확인할 수 있습니다. 이는 앞서 설명한 대로 정점 3과 4만 선택하면 모든 간선을 덮을 수 있기 때문입니다.