graph_tool.topology 3

아래 튜토리얼에서는 그래프에서의 매칭(matching), 특히 최대 매칭(maximum cardinality matching) 및 최대 가중치 매칭(maximum weighted matching)을 다룹니다. 이는 Boost C++ Libraries(C++에서 제공되는 고성능 그래프 라이브러리) 문서 일부로, graph-tool 등 파이썬 라이브러리에서도 이 개념을 차용하여 구현합니다.

튜토리얼에서는 다음을 중점적으로 설명합니다:

1. 매칭(Matching)의 정의와 유형
2. 에드몬즈(Edmonds) 알고리즘을 이용한 최대 매칭 계산 과정 개요
3. 가중치가 있는 그래프에서의 최대 가중치 매칭
4. 알고리즘 복잡도, 내부 구현 개념(Blossom, Dual 변수 등)

---

1. 매칭(Matching)의 기본 개념

매칭(Matching):

• ‘매칭’이란 그래프에서 간선들의 부분집합 (M\subseteq E) 중 “어떤 두 간선도 공통 정점을 공유하지 않는” 성질을 만족하는 것입니다.
• 즉, 매칭에 속한 모든 간선이 서로 겹치는 정점이 없어야 합니다.

최대 매칭(Maximum Cardinality Matching, MCM):

• 매칭 중에서 가장 많은 간선을 포함하는 매칭.
• 크기(간선 개수)가 최대인 매칭을 말합니다.
• 예: 한 매칭의 크기 = 간선 수. “최대 매칭” = 그 중 크기가 최대인 것.

최대 매칭 vs. 극대 매칭(Maximal Matching):

• ‘극대 매칭(maximal)’은 더 이상 매칭에 간선을 추가할 수 없는 매칭. (크기가 최대인지 여부와는 별개)
• ‘최대 매칭(maximum cardinality)’은 “가능한 모든 매칭 중 간선 수가 진짜 최대”인 것.
• 일반적으로 “최대 매칭”은 “극대 매칭”의 한 종류이지만, 반대는 아님.

---

2. Edmonds 알고리즘(에드몬즈) - 최대 매칭 계산

2.1 에드몬즈의 기본 아이디어: “증대 경로(Augmenting Path)”

1. 증대 경로(augmenting path)

   • 매칭에 속하지 않은 (free) 정점에서 시작→끝나는 경로 중, 매칭 간선과 비매칭 간선이 번갈아 나타나는 (matched, unmatched alternating) 경로.
   • 경로 길이가 홀수 개(2n+1개의 간선)이며, matched 간선이 n개, unmatched 간선이 n+1개.
   • 이 경로의 matched/unmatched를 뒤집으면 매칭의 크기가 +1 증가.

2. 기본 구조:

   • (1) 초기 매칭을 만든다. (예: 비어있는 매칭, 혹은 greedy등)
   • (2) 증대 경로를 찾으면, 매칭을 augment하여 크기를 +1.
   • (3) 더 이상 augmenting path가 없으면, 현재 매칭이 최대 매칭이다.

3. 문제: 일반 그래프에서 증대 경로 찾기 시, “블로섬(Blossom)” 등 복잡한 구조가 있음.

   • 에드몬즈 알고리즘은 이러한 “블로섬 축소(blossom shrinking)” 테크닉을 이용해 일반 그래프에서도 증대 경로를 찾고, 반복적으로 매칭 크기를 키워감.

2.2 구현 관점

• edmonds_maximum_cardinality_matching:

  • 무방향 그래프 (G)에서 최대 매칭을 찾아, 결과를 mateMap(정점→짝 정점) 형태로 저장.
  • 복잡도: (O(mn \alpha(m,n))), 여기서 (\alpha)는 Ackermann 역함수의 매우 느린 증가.
  • 결과로 mateMap[v] = 짝이 된 정점 (혹은 null_vertex()).

• checked_edmonds_maximum_cardinality_matching:

  • 동일하지만, 추가로 최종 매칭이 실제 최대 매칭인지 검증(verification) 절차를 수행해 true/false를 반환.
  • 검증에는 Tutte-Berge 공식과 Edmonds-Gallai decomposition 등의 그래프 이론이 사용됨.
  • 이 검증은 “알고리즘이 올바른지”를 믿을 수 있는 장점이 있음.

(A) 초기 매칭 생성 방법

1. empty_matching: O(n) 시간, 매칭이 비어 있음.
2. greedy_matching: 간선을 순회하며, 이미 매칭과 충돌 안 하면 매칭에 추가. O(m log n).
3. extra_greedy_matching: 간선을 “연결된 정점의 차수”로 정렬해, 차수 낮은 정점부터 매칭 추가. O(m log n) 정도.

(B) 증대 경로 찾기(Augmenting path finder)

• edmonds_augmenting_path_finder:
  • 블로섬 축소 등 구현. 한 번 찾을 때 O(m α(m,n))
• no_augmenting_path_finder:
  • 증대 경로를 찾지 않는(즉, 매칭을 늘리지 않는) 식으로 무시.

(C) 검증(Verifier)

1. maximum_cardinality_matching_verifier:
   • Tutte-Berge 이용, 실제 이 매칭이 최대인지 검사. O(m α(m,n))
2. no_matching_verifier: 항상 true 반환 (검증 안 함).

2.3 “matching()” 템플릿 함수

라이브러리 내부에는

matching<Graph, MateMap, VertexIndexMap,
         AugmentingPathFinder, InitialMatchingFinder, MatchingVerifier>
         (const Graph& g, MateMap mate, VertexIndexMap vm)

와 같은 제네릭 함수가 있으며,
edmonds_maximum_cardinality_matching 등은 이를 적절히 특수화해서 사용하는 inlined 버전.

예)

• edmonds_maximum_cardinality_matching = edmonds_augmenting_path_finder + extra_greedy_matching + no_matching_verifier
• checked_edmonds_maximum_cardinality_matching = edmonds_augmenting_path_finder + extra_greedy_matching + maximum_cardinality_matching_verifier.

---

3. 최대 가중치 매칭(Maximum Weighted Matching)

3.1 정의

• 각 간선 (e)에 가중치 (w_e)가 주어졌을 때, 매칭에 속한 간선들의 가중치 합 (\sum w_e)이 최대가 되는 매칭을 찾는 문제.
• 최대 매칭과 달리, 간선 개수 대신 “가중치 합”을 최대로 만듦.

3.2 알고리즘 (Edmonds+Dual 기반)

• maximum_weighted_matching:
  • Edmonds가 제안한 Blossom 알고리즘의 가중치 버전(1965).
  • 구현 세부에서 dual 변수(라벨) 등을 관리하며, primal-dual 방식으로 반복.
  • 복잡도: (O(n^3)) 수준 (단순 구현).
• brute_force_maximum_weighted_matching:
  • 가능한 매칭 전부를 탐색해 최댓값 찾는 극단적 방법. 지수시간.

3.3 구현상 주의: “Blossom 처리와 Dual 변수를 유지”

• 가중치가 있을 때는, 단순히 증대 경로만으로는 충분치 않고, dual 변수(정점 라벨, blossom 레벨 등)를 계속 업데이트 해야 함.
• Blossom이 중첩되거나, 축소/확장 시나리오가 훨씬 복잡해짐.

---

4. 알고리즘 복잡도 및 정리

• 에드몬즈 최대 매칭(cardinality)

  • 일반 그래프: (O(m n \alpha(m,n))).

• 에드몬즈 최대 가중치 매칭(weighted)

  • 단순 구현: (O(n^3)).
  • 최적화 논문: (\tilde{O}(n m + n^2 \log n)) 등의 결과도 있으나, Boost 라이브러리에는 미포함.

• mateMap에 매칭 결과로 각 정점의 짝을 저장:

  • mate[v] = w, mate[w] = v if ((v,w))가 매칭에 포함.

---

5. 예시 (C++)

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/max_cardinality_matching.hpp>
#include <iostream>

int main() {
    using namespace boost;
    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
    Graph g(6);

    // 예시: 간선 추가
    add_edge(0,1,g);
    add_edge(1,2,g);
    add_edge(2,3,g);
    add_edge(2,4,g);
    add_edge(4,5,g);

    // mate 배열(정점→정점)
    std::vector<graph_traits<Graph>::vertex_descriptor> mate(num_vertices(g),
                                                             graph_traits<Graph>::null_vertex());

    // 최대 매칭
    edmonds_maximum_cardinality_matching(g,
        make_iterator_property_map(mate.begin(), get(vertex_index,g)));

    // mate 정보 출력
    for (int v=0; v<6; v++){
        if (mate[v] == graph_traits<Graph>::null_vertex())
            std::cout << v << " is unmatched\n";
        else
            std::cout << v << " matched with " << mate[v] << "\n";
    }

    return 0;
}

이와 비슷한 방식으로 가중치가 있을 경우에는 maximum_weighted_matching() 함수에 edge_weight_t 프로퍼티가 있어야 하며, 그에 따라 mateMap을 구할 수 있습니다.

---

결론

• 매칭(Matching): 간선들이 공통 정점을 공유하지 않도록 선택.
• 최대 매칭(Max Cardinality Matching): 매칭된 간선 수를 최대화.
  • 구현: edmonds_maximum_cardinality_matching + optional ‘검증(checked_)’
  • 복잡도: (O(m n \alpha(m,n))).
• 최대 가중치 매칭(Maximum Weighted Matching): 간선 가중치 합을 최대화.
  • maximum_weighted_matching / brute_force_maximum_weighted_matching
  • 전자는 에드몬즈 기반, (O(n^3)) 정도.
• Boost 라이브러리에서는 mateMap(정점→짝 정점)을 통해 결과 표현.
• 사용자는 필요에 따라 “초기 매칭”, “증대 경로 탐색”, “검증” 알고리즘을 조합할 수 있음.

이로써 Edmonds 알고리즘(Blossom) 계열을 이용해 일반 그래프에서 최대 매칭/가중치 매칭을 효율적으로 구할 수 있으며, graph-tool 등 다양한 그래프 라이브러리에서도 유사한 구조로 제공되는 함수를 사용할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 max_cardinality_matching() 함수를 중심으로, 최대 매칭(최대 수의 간선으로 구성된 매칭) 혹은 “가중치가 주어졌을 경우 최대 가중치 매칭”을 어떻게 구하는지 설명합니다. 또한, 다양한 파라미터(bipartite, init_match, weight, heuristic, edges, 등)가 실제로 무엇을 의미하고, 어떤 상황에서 쓰이는지, 그리고 실용적인 예제 코드를 통해 알아봅니다.

튜토리얼의 흐름:

1. 문제 배경: 매칭과 최대 매칭의 개념
2. 함수 시그니처와 파라미터 설명
3. 함수 동작 방식 (예시: 무가중 / 가중 / 이분 그래프 / 휴리스틱 옵션)
4. 간단한 Python 예제 (graph-tool 코드 + 주석)
5. 추가 팁 및 주의사항

---

1. 매칭과 최대 매칭의 배경

• 매칭(Matching): 그래프 (G=(V, E))에서, 어떤 간선들의 부분집합 (M \subseteq E)을 택했을 때, 이 집합에 속한 간선들이 서로 어떤 정점도 겹치지 않는 상태.
  • 즉, 매칭에 포함된 간선들끼리는 공통 정점이 없어야 합니다.
• 최대 매칭(Maximum Matching): 가능한 매칭 중, 간선의 개수가 최대가 되는 매칭.
  • 예: 카드inality 기반의 최대 매칭.
• 최대 가중치 매칭(Maximum Weighted Matching): 각 간선이 가중치 (w(e))를 가질 때, 매칭에 포함된 간선들의 가중치 합을 최대로 하는 매칭.

graph-tool 라이브러리의 max_cardinality_matching() 함수는, 기본적으로 최대 (수)의 매칭을 찾지만, weight 파라미터가 주어지면 최대 가중치 + 최대 수를 동시에 만족하는 매칭을 찾습니다. (동점일 때는 최대 간선을 고르는지, 최대 가중을 우선하는지 등에 대한 구현 세부는 Boost 라이브러리 문서 참고)

---

2. max_cardinality_matching() 함수 시그니처와 파라미터

match = graph_tool.topology.max_cardinality_matching(
    g,
    weight=None,
    bipartite=False,
    init_match='extra_greedy',
    heuristic=False,
    minimize=False,
    edges=False,
    brute_force=False
)

• g: 사용될 그래프(Graph 객체).

  • 무방향 그래프여야 합니다(유향 그래프라면 매칭 개념이 다르게 적용되거나 에러).

• weight=None:

  • None이면, 간단히 최대 간선 수(카디널리티) 매칭을 찾음.
  • EdgePropertyMap 객체를 넣으면, “최대 매칭이면서 동시에 가중치 합을 최대(또는 최소)로” 하는 매칭을 찾음.

• bipartite=False:

  • 만약 이분 그래프라면 True로 설정 or 정점 속성(VertexPropertyMap)으로 이분 분할을 지정.
  • 이분 그래프일 때 알고리즘이 좀 더 효율적으로 동작할 수 있음.

• init_match='extra_greedy':

  • 매칭을 시작하기 전, 초기 매칭을 어떻게 구할지 결정하는 옵션.
  • 'empty', 'greedy', 'extra_greedy' 중 선택 가능.
  • 무게가 없고(weight=None), heuristic=False일 때만 유효.

• heuristic=False:

  • True면, 빠른(선형 시간) 휴리스틱이 수행되어 근사 매칭(정확히 최대가 아닐 수도!)을 구함.
  • 대규모 그래프에서 매우 빠른 매칭이 필요할 때 유용.

• minimize=False:

  • weight가 주어졌을 때, 최대 혹은 최소 가중치 매칭을 결정하는 플래그.
  • True면 “최소 가중치 매칭”, False면 “최대 가중치 매칭”.

• edges=False:

  • 기본적으로 리턴값은 정점별 매칭 상대를 가리키는 VertexPropertyMap.
  • 만약 True라면, 매칭에 속한 간선 여부를 표시하는 EdgePropertyMap(bool)이 반환.

• brute_force=False:

  • weight가 있고, heuristic=False인 경우, True로 두면 느린 무차별 대입(브루트 포스) 방법을 씀(아주 작은 그래프 테스트용).

복잡도:

• 일반적으로 (O(m \cdot n \cdot \alpha(m,n))) (단, (\alpha)는 매우 느리게 증가하는 함수)
• 가중치 매칭의 경우 (O(n^3)).
• 휴리스틱(heuristic=True) 시, (O(n+m)) 선형 시간.
• 브루트포스(brute_force=True)는 지수 시간.

---

3. 함수 동작 요약

1. 무가중 그래프 (기본)

   • Edmonds’ Blossom 알고리즘 기반으로 “최대 카디널리티 매칭”을 구함.
   • (O(mn\alpha(m,n))) 시간.

2. 가중치 그래프 (weight != None)

   • “최대 가중치”(+ 최대 간선 수도 고려)의 매칭을 구하기 위해 Edmonds’의 가중치 알고리즘(Primal-dual, Blossom) 등 활용.
   • 시간 복잡도 (O(n^3)) (더 빠른 방법도 있으나, Boost 구현은 이 방식을 취함).

3. 이분 그래프 (bipartite=True or bipartite=vertex_prop)

   • 이분 매칭을 위한 Hopkroft–Karp 등에 준하는 최적화가 가능.
   • 그래프가 실제 이분인지 / vertex_prop로 파티션을 지정해야 최적 성능 발휘.

4. Heuristic 모드 (heuristic=True)

   • 큰 그래프에서 근사 매칭(정확도는 떨어질 수 있음)이지만, 선형 시간에 근접한 빠른 알고리즘으로 구함.

5. 리턴 형태

   • edges=False: VertexPropertyMap (각 정점이 매칭된 상대 정점 or null_vertex)
   • edges=True: EdgePropertyMap(bool) (매칭에 속한 간선만 True)

---

4. 실습: 파이썬 코드 예제

다음 예시는 graph-tool 라이브러리에서의 max_cardinality_matching() 함수를 사용해본 스크립트입니다. (단, 실제 사용 전 import graph_tool.all as gt, import numpy as np 같은 import가 필요합니다.)

예제 1: 무가중 그래프에서 최대 매칭

import graph_tool.all as gt
import numpy as np

def example_unweighted_matching():
    # 1) 임의 그래프 생성(Price network 300노드) -> 무방향 View
    g_orig = gt.price_network(300)
    g = gt.GraphView(g_orig, directed=False)  # 무방향으로 보기

    # 2) max_cardinality_matching 실행 (edges=True로 간선 property map 리턴)
    matching_eprop = gt.max_cardinality_matching(g, edges=True)

    # 매칭된 간선 수 카운트
    num_matched_edges = sum(1 for e in g.edges() if matching_eprop[e])
    print(f"Found matching with {num_matched_edges} edges.")

    # (A) EdgePropertyMap(float) 생성
    penwidth_ep = g.new_edge_property("float")
    
    # matching_eprop[a] -> True/False이므로, True면 3.0, False면 1.0으로 설정
    # (원한다면 더 복잡한 수식 가능)
    for e in g.edges():
        if matching_eprop[e]:
            penwidth_ep[e] = 3.0  # 매칭 간선 굵게
        else:
            penwidth_ep[e] = 1.0  # 비매칭 간선 얇게

    # 3) 그래프 시각화
    pos = gt.sfdp_layout(g)
    gt.graph_draw(
        g,
        pos=pos,
        edge_color=matching_eprop,      # True->기본 colormap을 통해 다른색
        edge_pen_width=penwidth_ep,     # EdgePropertyMap(float)
        vertex_fill_color="lightgrey",
        output="max_match_example1.pdf"
    )

if __name__=="__main__":
    example_unweighted_matching()

주요 포인트:

• edges=True로 설정했으므로, 반환값이 EdgePropertyMap.
• matching_eprop[e] == True 면 해당 간선이 매칭에 속함.
• 매칭된 간선 수 = ( ) edges in the matching.

예제 2: 가중 그래프에서 최대 가중치 매칭

import graph_tool.all as gt
import numpy as np

def example_weighted_matching():
    # 1) 무작위 그래프 생성
    g = gt.random_graph(50, lambda: np.random.poisson(3), directed=False)
    
    # 2) 간선 weight 속성 만들기
    weight_ep = g.new_edge_property("double")
    import random
    for e in g.edges():
        weight_ep[e] = random.uniform(1,10)
    
    # 3) 최대 가중치 매칭 구하기
    match_vprop = gt.max_cardinality_matching(
        g, 
        weight=weight_ep, 
        minimize=False,  # 최대화
        edges=False      # 정점기준 매칭정보 반환
    )
    
    # 4) 매칭된 정점 수
    #    match_vprop[v] 가 None이 아니면 매칭된 것
    matched_count = sum(1 for v in g.vertices() if match_vprop[v] is not None)
    print(f"Matched {matched_count} vertices (out of {g.num_vertices()}).")
    
    # 5) 매칭된 에지들의 weight 합계
    total_weight = 0
    used = set()
    for v in g.vertices():
        mate = match_vprop[v]
        if mate is not None:
            # v와 mate 사이의 edge 찾기:
            e = None
            for e_out in v.out_edges():
                # 무방향 그래프이므로 source/target 관계 유의
                if e_out.target() == mate or e_out.source() == mate:
                    e = e_out
                    break
            if e is not None:
                # 중복 방지
                if e not in used:
                    total_weight += weight_ep[e]
                    used.add(e)
    print(f"Total matching weight = {total_weight}")

if __name__=="__main__":
    example_weighted_matching()

예제 3: 이분 그래프 옵션 사용

이분 그래프(bipartite)일 경우, 조금 더 효율적인 알고리즘(예: Hopkroft-Karp 유사)이 적용될 수 있습니다. 이때, bipartite=True 또는 bipartite=vertex_color_prop 같이 설정합니다.

def example_bipartite():
    # bipartite 예시: 두 그룹(A,B)
    #  - A = 0~19, B=20~39
    #  - 임의 edges: A->B 만 존재
    g = gt.Graph(directed=False)
    g.add_vertex(40)
    bip_prop = g.new_vertex_property("bool")  # True/False로 구분
    for v in g.vertices():
        idx = int(v)
        if idx<20:
            bip_prop[v] = True
        else:
            bip_prop[v] = False
    import random
    for i in range(20):
        for j in range(20,40):
            # p=0.2 확률로 간선 생성
            if random.random()<0.2:
                g.add_edge(g.vertex(i), g.vertex(j))
    
    # 이제 bipartite 모드
    match_ep = gt.max_cardinality_matching(
        g,
        bipartite=bip_prop,
        edges=True
    )
    
    matched_edges = sum(1 for e in g.edges() if match_ep[e])
    print(f"Bipartite matching edges: {matched_edges}")

---

5. 추가 팁 및 주의사항

1. init_match 옵션 ('empty', 'greedy', 'extra_greedy'):
   • weight가 없고, heuristic=False일 때만 유효.
   • 'empty'는 초기 매칭 없이 시작.
   • 'greedy'는 에지 순회하며 갈 수 있으면 매칭에 추가.
   • 'extra_greedy'는 간선을 “정점 차수” 기반 정렬 후 그리디 식으로 매칭해 초기화 -> 품질이 나아질 수 있음.
2. heuristic=True
   • 정확히 최대 매칭인지 보장 안 됨. 대신 선형 시간으로 매우 빠름.
   • 대규모 그래프에서 근사해가 필요할 때 좋음.
3. 가중치 + 최대 매칭
   • weight != None이면, “간선 개수 최대” AND “가중치 합 최대”를 동시에 달성하려 시도(Boost 문서상).
   • minimize=True이면 “가중치 합 최소” 쪽으로.
4. bipartite
   • 일반 그래프보다 이분 그래프에서의 매칭 계산은 더 효율적.
   • bipartite=False일 경우, 일반 Edmonds Blossom Algorithm 사용.
5. 결과 해석
   • edges=True일 경우: EdgePropertyMap (bool). True=매칭에 포함된 간선.
   • edges=False일 경우: VertexPropertyMap (각 정점이 매칭된 상대 정점 or gt.INVALID).
6. 시간복잡도
   • 일반 무가중: (O(mn \alpha(m,n))).
   • 가중치: (O(n^3)).
   • 휴리스틱(heuristic=True): (O(n+m)).
   • 브루트포스: 지수적 시간.
7. 알고리즘 이론
   • 메인 아이디어는 Edmonds의 “Blossom 알고리즘” (1965) 기반.
   • 가중치 버전은 “Blossom + Primal-Dual” 기법.

---

정리

max_cardinality_matching()는 그래프에서 최대 매칭(혹은 최대/최소 가중치 매칭)을 손쉽게 구하는 강력한 함수입니다.

• 단, 그래프가 너무 크면 일반 알고리즘(Edmonds)이 (\mathcal{O}(n^3))급(가중치 포함 시)이라 다소 느릴 수 있음.
• 이분 그래프이거나, 휴리스틱 모드를 쓰면 훨씬 빠르게 근사해를 구할 수 있음.

실제 도시 교통 네트워크, 대규모 bipartite matching(예: job-person 매칭), 병렬 분산처리 로드매칭, 공유자원 할당 등 다양한 응용에서 활용 가능하니, 상황에 맞춰 파라미터를 조정하면 됩니다.

이상으로, max_cardinality_matching() 함수의 주요 개념과 사용 예시를 살펴봤습니다.

아래 내용은 Michael Luby의 논문 "A Simple Parallel Algorithm for the Maximal Independent Set Problem" (이하 MIS 문제) 관련 일부 발췌입니다. 여기서 소개된 알고리즘들은 그래프의 최대 독립 집합(Maximal Independent Set, 이하 MIS)을 빠른 병렬 알고리즘으로 구하는 방법을 다룹니다. 다음 설명에서는 해당 논문의 핵심 수식, 개념, 알고리즘 구조, 분석 원리 등을 최대한 상세하게 정리해보겠습니다.

---

1. 문제 정의와 배경

1.1. Maximal Independent Set (MIS) 문제

• 독립 집합(Independent Set): 무방향 그래프 ( G = (V, E) )에서, 어떤 정점 집합 ( I \subseteq V )가 서로 간에 인접한 정점을 포함하지 않을 때 이를 독립 집합이라 함.
• 최대 독립 집합(Maximal Independent Set, MIS): 독립 집합 중에서 더 이상 어떤 정점을 추가하여도 독립성이 유지되지 않도록, 즉 "확장이 불가능"한(=맥시멀) 독립 집합.
  (\rightarrow) 주의: '최대(maximal)'와 '최대 크기(maximum)'는 다른 개념임. 여기서 "maximal"은 국소적으로 더 확장할 수 없는 집합을 의미하고, "maximum"은 크기가 전역적으로 최대인 독립 집합을 의미.

1.2. 병렬 알고리즘(Parallel Algorithm)

• 병렬 모델: 논문에서는 EREW PRAM(Exclusive-Read Exclusive-Write 병렬 RAM)을 가정. 즉, 여러 프로세서가 동시에 동일 메모리 위치를 읽거나 쓰는 연산을 허용하지 않는다.
• 목표: 순차 알고리즘은 ( O(n + m) ) 정도로 간단하지만, 이를 병렬화하는 것은 단순 시뮬레이션으로는 어렵다(특히 "사전식(Lexicographically first) 독립집합"을 구하는 문제는 NC-완으로 알려짐).

Luby의 핵심 공헌:
1. 무작위(Monte Carlo) 기반의 지역적(local) 알고리즘 제시
2. 해당 무작위 알고리즘을 쌍wise 독립(pairwise independence) 만으로도 충분하다는 점을 보여, 보다 적은 난수로도 동일한 분석이 가능함을 증명
3. 이러한 기법을 통해 최종적으로 결정적(deterministic) NC(^2) 알고리즘 구성.

---

2. 몬테카를로 알고리즘(기본 아이디어)

2.1. 무작위 기반 단계

논문에서 제시된 1차 알고리즘(가장 간단 버전)은 다음과 같이 요약된다 (구체화):

1. ( G' \leftarrow G ) (현재 그래프). ( I \leftarrow \emptyset ) (독립 집합 후보).
2. While ( G' )가 간선이 남아있으면(혹은 정점이 남아있으면):
   1. (무작위 선택) 각 정점 ( v \in V' )에 대해,
      [
      \text{정해진 확률 } p(v) = \frac{1}{2\,d(v)}
      \quad (\text{등 다양한 수식으로 정의될 수 있음})
      ]
      를 기준으로, 독립집합 후보에 ( v )를 추가(혹은 제외)하는 이벤트를 독립적으로 발생시킴.
      • 실제 논문 본문에서는 ( p(v) = \frac{1}{2d(v)} ) 같은 꼴을 제안했으며, 이때 서로 간 mutually independent 가정.
   2. 새로 ( I' \subset V' ) (이번 라운드에서 추가된 집합)과, ( I' )에 인접한 정점 ( N(I') )를 모두 제거
      • 즉, ( I \gets I \cup I' ),
      • 그리고 ( V' \gets V' \setminus \bigl(I' \cup N(I')\bigr) ).
   3. 이 과정을 반복.
3. 종료 시 ( I )는 더 이상 확장할 수 없는 독립 집합이므로, MIS가 됨.

(서술)

• 위 루프 한 번을 "한 라운드" 혹은 "한 단계"라고 부름.
• 각 라운드에서 가정: (\forall v,) 이벤트 (E_v) = “정점 (v)가 이번 라운드에 독립집합 후보로 선택됨”이 상호 독립.
• 하지만 실제로는 상호 독립이 엄청난 난수를 요구. Luby는 쌍wise 독립만으로도 동일 분석이 가능함을 보여줌 (4장 참조).

2.2. 분석 개괄

• 라운드 한 번마다(=while loop 1회), 적어도 “어느 정도 비율의 간선”이 사라진다고 증명 (\Rightarrow) 대략 (\log n) 번 정도면 간선이 다 제거됨.
• EREW PRAM에서 각 라운드 구현 시간은 (O(\log n))로 가능(병렬로 degree 계산, 무작위생성 등).
  (\therefore) 전체 기대 시간 (O((\log n)^2)).

---

3. 쌍wise 독립(Pairwise Independence)와 결정적 변환

3.1. 쌍wise 독립의 필요성

• 엄밀하게 ‘모든 정점 이벤트가 상호 독립’이면 난수비트가 (n)개 이상 필요 -> 매우 커짐.
• 하지만 알고리즘 분석을 자세히 보면, 서로 다른 정점 (v, w)의 이벤트 ({E_v, E_w}) 쌍 간의 독립성만 보장되어도(상호 독립 전부는 불필요), 핵심 증명 가능 (이게 4장에 자세히).

3.2. 쌍wise 독립 난수 생성

Luby 논문(5장)에서 정점 개수 (n)에 대해 (O(n^2))개의 이진 벡터만 택하는 “작은 샘플 공간(small sample space)”을 구성하고, 그 중에서 “쌍wise 독립” 사건을 만족하는 방식으로 난수를 생성한다:

1. 소수 (q)를 (n \le q < 2n) 범위서 선택.
2. (n \times q) 크기 행렬 (A) 생성: (세부는 논문 본문)
3. 각 라운드마다 ((x, y)\in {0,1,\dots,q-1}^2)를 골라 행렬을 통해 비트벡터 (\mathbf{b}_{x,y})를 만든다.
4. (\mathbf{b}_{x,y})를 확률 (\frac{1}{q^2})로 골고루 선택하면, 각 정점 이벤트가 pairwise independence를 만족.
5. 최종적으로, 모든 ((x,y)) 쌍을 병렬로 시도해 가장 좋은 결과(= 간선이 최대한 많이 제거됨)를 택하면 결정적 알고리즘.

요약하면:

• (1) “쌍wise 독립”만으로도 MIS 알고리즘 분석에 유효
• (2) “쌍wise 독립” 난수는 매우 적은 비트/메모리로 생성 가능.
• (3) 병렬로 ({0,\dots,q-1}^2)를 전부 시도하면(= (O(n^2)) 샘플 모두 시도), 무작위가 아니라도, 항상 좋은 라운드 성능 보장 -> 결과적으로 결정적 (NC^2) 알고리즘 완성.

---

4. 결정적(Dererministic) 알고리즘 (NC(^2) 내부)

4.1. 알고리즘 구성

정리하자면, Luby 최종 결정적 알고리즘 개요:

1. 그래프 (G'=(V',E')) 초기화 ((G' \leftarrow G)).
2. While (G')에 간선 혹은 정점이 남아있으면:
   1. (Case A) 만약 어떤 정점 (v\in V')에서 (d(v) \le \frac{n}{2}) 같은 threshold 조건이 성립하면(논문에 따라 다른 임계값 사용),
      • 그런 (v)를 바로 독립 집합 (I)에 추가 후 (v)와 인접한 정점을 (G')에서 제거
   2. (Case B) 그렇지 않으면(=모든 정점 차수가 임계값 이상), 미리 구성해 둔 “쌍wise 독립 샘플 공간” ({\mathbf{b}^{(k)}}_{k=1..O(n^2)}) 전체를 시도:
      • 각 (\mathbf{b}^{(k)})에 따라, 라운드에서 독립 집합 후보 (I'\subset V') 결정
      • 그때 제거되는 간선 수 (|E'(I')|)가 가장 큰 (\mathbf{b})를 골라, 그 라운드의 (I')로 결정.
   3. (I \leftarrow I \cup I'), (V' \leftarrow V' \setminus (I'\cup N(I'))).
3. 반복 종료 시 (I)는 Maximal Independent Set.

4.2. 시간 복잡도

• 한 라운드에서:
  • (\mathbf{b}^{(k)}) (O(n^2))개를 전부 시도.
  • 각 시도마다 정점별로 (\mathbf{b}^{(k)}) 참조 + 병렬로 인접성 검사 -> (O(\log n)) 안에 “추가될 집합 (I')” 및 제거 간선 개수를 산출 가능(EREW PRAM (O(m)) 프로세서).
• 전체 라운드 횟수는 (O(\log n)).
• 따라서 전체 결정적 알고리즘은 (O((\log n)^2)) 시간, (O(mn^2)) 프로세서(단순 구현 시).

(논문에서는 조금 더 정교한 병렬화를 통해 프로세서 수를 줄일 수 있다고도 언급.)

---

5. 기타 관련 문제 및 의의

5.1. Maximal Coloring

• 그래프에서 (정점 v당 사용할 수 있는 색 집합 (C_v))를 주고, “인접한 두 정점은 같은 색을 쓰면 안 된다 + 색을 안 쓴 정점은 자기 이웃 중에 그 색을 쓰는 애가 있어야 한다” 라는 맥시멀 색칠 문제.
• MIS의 특수 케이스로 환원 가능(= (NC^2) 해결).

5.2. Distributed Computing / AI 시사점

• Luby의 첫 번째 몬테카를로 알고리즘(3장)은 각 정점이 '이웃 정보'만 가지고 국소 결정 하는 특징이 있음. 분산 네트워크나 연결주의 모델(인공신경망)에서 노드가 local rule로 작동한다는 점에서 매우 유용.

5.3. 여전히 남은 질문

• MIS 병렬 알고리즘의 하한(= lower bound)은 어떻게 되는가?
• DTML(“다수와 다른 레이블” 문제)과 같이 MIS와 유사해 보이지만 여전히 NC에서 풀 수 있는지 미결인 문제 존재.

---

6. 결론 및 요약

Michael Luby 논문에서 제안된 단순 병렬 알고리즘의 핵심은 다음과 같다:

1. 기본 구조:

   • 각 라운드에서 확률적으로 독립집합 후보 (I')를 뽑아서(정점별로 무작위 이벤트), (I'\cup N(I'))를 그래프에서 제거.
   • 이를 반복하면 (O(\log n)) 라운드 안에 맥시멀 독립 집합 완성.

2. 상호 독립(mutual independence)이 아니어도, 쌍wise 독립(pairwise)만 보장되면 동일 분석이 유지됨을 보임.

3. 쌍wise 독립 난수를 만드는 기법:

   • (O(n^2))개 이진 벡터로 이뤄진 작은 샘플 공간 구성.
   • 각 정점 이벤트가 그 중 임의 벡터에서의 bit로 결정되도록 설계.
   • 이로써 기존에 필요하던 (n)비트가 아닌, (\log(n^2)\approx 2\log n) 비트만으로도 충분.

4. 결정적 알고리즘:

   • 모든 샘플((O(n^2))개)을 라운드마다 병렬로 시도하고, “가장 간선 제거 효과 큰 샘플”을 택하면, 무작위가 아니라도(=결정론적) (\log n)번 라운드 이내로 수렴.
   • EREW PRAM 상에서 (O((\log n)^2)) 시간, 다소 큰 프로세서 수((O(mn^2)))가 필요.

이를 통해, MIS 문제를 NC(^2) 클래스에서 풀 수 있음을 보인다. 이 결과는 기존에 Karp&Wigderson 등이 (O((\log n)^2)) 병렬 시간에 비해 알고리즘 구조가 단순하고, 쌍wise 독립성만 필요하다는 점에서 이론적·실용적 의의를 지닌다.

---

참고 문헌 (논문 본문 내)

• [KW] R. Karp and A. Wigderson, A Fast Parallel Algorithm for the Maximal Independent Set Problem, 16th STOC (1984).
• [ABI] N. Alon, L. Babai, A. Itai, ...
• [Va], [Co], [IS], [II], [KSS], etc. (본문)

(이상, Luby(1985) 논문 내용을 정리.)

아래는 graph-tool 라이브러리에 포함된 max_independent_vertex_set() 함수를 사용하여 그래프에서 맥시멀 독립 정점 집합(MIVS, Maximal Independent Vertex Set)을 효율적으로 구하는 방법을 설명합니다. 이 함수는 Michael Luby가 제안한 유명한 병렬 MIS(Maximal Independent Set) 알고리즘 아이디어 ([mivs-luby])를 기반으로 구현되어 있으며, 시간복잡도는 그래프 (G)의 정점 수를 (n), 간선 수를 (m)라 할 때 (O(m)) 또는 (O(n + m)) 수준으로 동작하도록 되어 있습니다. 아래 튜토리얼에서는 이 함수의 내부 작동원리, 파라미터 옵션, 활용 예시 파이썬 코드 등을 단계별로 정성껏 소개해봅니다.

---

1. 문제 배경 및 개념 정리

1. 독립 정점 집합

   • 정의: 무방향 그래프 (G=(V, E))에서, 어떤 정점 집합 (S \subseteq V) 내의 임의의 두 정점 간에 간선이 존재하지 않는다면, (S)는 독립 정점 집합(Independent Vertex Set)이라고 합니다.
     [
     \forall u, v \in S,\ (u,v)\notin E
     ]

2. 맥시멀 독립 집합(MIVS)

   • 정의: 더 이상 어떤 정점도 추가로 포함할 수 없는(= 확장 불가능한) 독립 집합. 즉, (S\subseteq V)가 독립이고, (V\setminus S) 어디서도 정점을 추가하면 독립성이 깨지므로, (S)는 맥시멀 독립 집합.
   • 맥시멀(Maximal)과 최대(Mimum)은 다른 개념임을 주의하세요. 전자는 “더 이상 확장 불가능”이고, 후자는 “크기가 전역적으로 최대”를 의미함.

3. 맥시멀 독립 집합의 활용

   • 예: 그래프 Coloring, Matching, Clustering, Scheduling 등 다양한 문제에서 핵심 서브루틴으로 쓰임.
   • Michael Luby ([mivs-luby])는 병렬 알고리즘 맥락에서 (\log)-스케일 반복으로 빠르게 MIVS를 구성하는 방법을 제안하였음. graph_tool.topology.max_independent_vertex_set()도 유사한 아이디어로 구현.

---

2. graph-tool의 max_independent_vertex_set() 함수 설명

2.1 함수 시그니처

mivs_property_map = gt.max_independent_vertex_set(
    g,
    high_deg=False,
    mivs=None
)

• 인자 설명:

  • g: 사용될 그래프 객체(Graph 또는 GraphView).
  • high_deg (bool, default: False):
    • True면 높은 차수(degree)의 정점을 먼저 집합에 포함하려 시도.
    • False면 낮은 차수 정점을 먼저 포함하려 시도.
    • Luby 알고리즘 변형 중 하나로서, 어떤 정점을 우선 택하느냐에 따라 성능 차이가 있을 수 있음.
  • mivs (VertexPropertyMap, 옵션):
    • 이미 만들어 둔 Boolean형 정점 property map에 결과를 저장하고 싶다면 제공.
    • 제공되지 않으면 내부적으로 새 property map을 만들고 반환.

• 반환:

  • mivs: Boolean 타입의 정점 property map. 각 정점에 대해 True이면 그 정점이 맥시멀 독립 집합에 속함.

2.2 내부 알고리즘 개요

1. 확률적 혹은 순차적인 규칙에 따라 정점을 독립 집합 후보로 선정.
2. 후보로 선정된 정점과 그 정점에 인접한 정점들을 그래프에서 제거.
3. 남은 그래프에 대해 반복 → 최종적으로 확장 불가능 상태가 되면 MIVS 완성.

이는 Luby ([mivs-luby])가 제안한 병렬 알고리즘과 유사한 구조입니다. graph-tool에서는 이 과정을 단일 스레드/순차로도 충분히 빠르게 구현하지만, 원리적으로는 병렬성(EREW PRAM 분석 시 (\log n) 라운드 등)도 활용 가능합니다.

---

3. 튜토리얼: 사용 예시 코드

아래는 max_independent_vertex_set() 함수를 간단히 써보는 예시입니다.

import graph_tool.all as gt

def example_mivs():
    # 1) 예시 그래프 생성: Price network 300개 노드 (방향성 제거)
    g_orig = gt.price_network(300)
    g = gt.GraphView(g_orig, directed=False)  # 무방향 그래프로 보기
    
    # 2) 맥시멀 독립 정점 집합 구하기
    # high_deg = False -> 낮은 차수 정점 우선 버전
    mivs_map = gt.max_independent_vertex_set(g, high_deg=False)
    
    # mivs_map[v] == True 면, v가 독립 집합에 속함
    mivs_size = sum(1 for v in g.vertices() if mivs_map[v])
    print(f"Found a maximal independent set of size {mivs_size}")

    # 3) 시각화
    #   - 독립 집합에 속한 정점은 파랑 / 속하지 않은 정점은 회색
    #   - edges 그대로
    pos = gt.sfdp_layout(g)
    # Boolean값 -> color로 매핑
    #   True -> 노란색, False -> 회색
    color_map = g.new_vertex_property("string")
    for v in g.vertices():
        color_map[v] = "yellow" if mivs_map[v] else "gray"
    
    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=color_map,
        vertex_color=color_map,
        output="mivs_example.pdf"
    )

if __name__ == "__main__":
    example_mivs()

코드 주석 상세:

1. 그래프 준비:
   • price_network(300) : Price model 그래프(= 무방향 Preferential Attachment 유사).
   • GraphView로 directed=False 하여 무방향으로 취급.
2. 맥시멀 독립 정점 집합:
   • gt.max_independent_vertex_set(g, high_deg=False) 호출 → Boolean vertex map 반환.
3. 결과 확인:
   • mivs_size = sum(mivs_map[v] for v in g.vertices())
   • 독립 집합의 크기, 혹은 결과 시각화.

---

4. 파라미터 high_deg=True vs False

• high_deg=True:
  • 차수가 큰 정점을 우선 포함.
  • 직관적으로, 차수가 큰 정점을 제거하면 많은 인접 정점이 함께 제외되므로 빠르게 수렴 가능?
  • 하지만 특정 그래프 구조에 따라 성능 차이가 있을 수 있음.
• high_deg=False (기본값):
  • 차수가 낮은 정점을 먼저 포함 → 여러 가지 실험적, 이론적 장단이 존재.

일반적으로 두 옵션 중 큰 차이가 없을 수도 있으니, 필요에 따라 테스트를 권장합니다.

---

5. 알고리즘 복잡도

• 이론적: Luby 알고리즘 원리에 따르면, 기대치 (\tilde{O}(\log n)) 라운드 안에 독립 집합을 완성(병렬 모델에서).
• graph-tool 구현에서는 단일쓰레드일 때도 (O(n+m)) 수준으로 충분히 빠르게 동작하도록 최적화.
• 대규모 sparse 그래프(에지 수 (m \approx n))에서 특히 빠름.

---

6. 관련 참고

• [mivs-luby] Luby, M. (1985). “A simple parallel algorithm for the maximal independent set problem”. Proc. 17th Symposium on Theory of Computing, ACM, pp. 1–10.
• [mivs-wikipedia] 일반적인 독립 집합 이론: https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29.

---

7. 요약 및 마무리

graph_tool.topology.max_independent_vertex_set() 함수는 단일 함수 호출로 그래프의 맥시멀 독립 정점 집합을 구할 수 있는 매우 편리한 기능입니다. 내부적으로 Luby 방식(혹은 유사한 방식)의 무작위/순차 알고리즘이 최적화되어 있고, high_deg 같은 옵션으로 약간의 변형을 줄 수 있습니다. 결과물은 Boolean형 vertex property map이므로, 이를 활용하여 시각화나 후처리를 손쉽게 할 수 있습니다.

맥시멀 독립 집합은 그래프 Coloring, Matching, 분산 알고리즘(네트워크 토폴로지 제어), 인공신경망(에너지 최소화), 스케줄링 등의 여러 문제에서 핵심 도구로 쓰이므로, 본 함수를 유용하게 쓸 수 있습니다.

이상으로 max_independent_vertex_set()의 사용법과 예시 코드를 마칩니다. 필요시 더 다양한 그래프에 적용하며 성능/결과를 살펴보시길 권장합니다.