매트로이드 교집합

문제 정의

같은 바탕 집합 \(E\) 위의 두 매트로이드 \(M_1 = (E, \mathcal{I}_1)\), \(M_2 = (E, \mathcal{I}_2)\)가 있다. 매트로이드 교집합 문제는

$$ \max\{ |S| : S \in \mathcal{I}_1 \cap \mathcal{I}_2 \} $$

를 찾는 것. 즉 두 독립성 제약을 동시에 만족하는 최대 집합.

주의: \(\mathcal{I}_1 \cap \mathcal{I}_2\) 자체는 보통 매트로이드가 아니다. 그래서 단일 그리디가 통하지 않고 별도 알고리즘이 필요하다.

왜 강력한가

많은 고전 문제가 두 매트로이드 교집합으로 환원된다.

이분 매칭이 특수 사례라는 점이 교집합의 일반성을 보여준다.

교환 그래프(exchange graph)

현재 공통 독립 집합 \(S\)가 있을 때, 교환 그래프 \(D_S\)를 만든다. 정점은 \(E\), 간선은:

• \(y \in S\), \(x \notin S\)에 대해 \(S - y + x \in \mathcal{I}_1\)이면 \(y \to x\) 간선.
• \(S - y + x \in \mathcal{I}_2\)이면 \(x \to y\) 간선.

또 두 종류의 "출발/도착" 집합:

• \(X_1 = \{x \notin S : S + x \in \mathcal{I}_1\}\) (\(M_1\) 기준 그냥 추가 가능)
• \(X_2 = \{x \notin S : S + x \in \mathcal{I}_2\}\)

증강(augmenting) 정리

정리(Lawler). \(X_1\)에서 \(X_2\)로 가는 \(D_S\)의 최단 경로 \(P\)가 존재하면, \(S \triangle V(P)\)(대칭차)는 크기가 \(|S|+1\)인 공통 독립 집합이다. 그런 경로가 없으면 \(S\)가 최대.

여기서 최단 경로(간선 수 최소, chordless)여야 한다는 조건이 중요하다. 최단성이 깨지면 대칭차가 독립성을 잃을 수 있다.

정당성의 핵심 보조정리

최단 경로 \(x_0 \to y_1 \to x_1 \to \dots \to x_k\) (\(x_0 \in X_1, x_k \in X_2\))에서, \(M_1\) 쪽 교환을 차례로 적용하면 유일 매칭 성질(unique perfect matching in the exchange subgraph) 덕분에 독립성이 보존된다. 최단 경로는 "지름길 간선"이 없어 이 유일성을 보장한다. 두 매트로이드 각각에 대해 교환 공리를 한 단계씩 적용한 결과가 합쳐져 \(|S|+1\) 독립 집합이 된다.

알고리즘 골격

S = 빈 집합
반복:
    교환 그래프 D_S 구성
    X1 → X2 최단 경로 BFS
    경로 없으면 종료
    S = S ⊕ V(경로)

각 증강이 \(S\)를 1 키우므로 최대 \(r = \min(r_1, r_2)\)번. 다음 강의에서 복잡도와 구현.

오라클 인터페이스

알고리즘은 두 독립성 오라클 만 알면 된다.

// S(현재 집합)에 대해 S - y + x 가 M_k에서 독립인가?
bool indep1(const vector<int>& S, int x, int y);  // y == -1 이면 단순 S + x
bool indep2(const vector<int>& S, int x, int y);

예) 그래프 매트로이드: "간선 집합이 숲인가"를 union-find로. 분할 매트로이드: 색별 카운트로.

한 번의 증강

bool augment(vector<int>& S, int n /*전체 원소 수*/) {
    vector<char> inS(n, 0);
    for (int e : S) inS[e] = 1;

    // 출발/도착 집합
    vector<int> X1, X2;
    for (int x = 0; x < n; x++) if (!inS[x]) {
        if (indep1(S, x, -1)) X1.push_back(x);
        if (indep2(S, x, -1)) X2.push_back(x);
    }
    // 교환 그래프 인접 리스트
    vector<vector<int>> adj(n);
    for (int y : S) for (int x = 0; x < n; x++) if (!inS[x]) {
        if (indep1(S, x, y)) adj[y].push_back(x);   // y -> x (M1)
        if (indep2(S, x, y)) adj[x].push_back(y);   // x -> y (M2)
    }
    // X1에서 BFS로 X2까지 최단 경로
    vector<int> par(n, -2);
    queue<int> q;
    for (int s : X1) { par[s] = -1; q.push(s); }
    vector<char> isX2(n, 0);
    for (int t : X2) isX2[t] = 1;
    int dest = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (isX2[u]) { dest = u; break; }   // BFS라 최단 보장
        for (int v : adj[u]) if (par[v] == -2) {
            par[v] = u; q.push(v);
        }
    }
    if (dest == -1) return false;           // 최대 도달
    // 경로 위 원소 토글(대칭차)
    for (int v = dest; v != -1; v = par[v]) inS[v] ^= 1;
    S.clear();
    for (int e = 0; e < n; e++) if (inS[e]) S.push_back(e);
    return true;
}

BFS는 간선 수 최소 경로를 주므로 "최단 경로" 조건을 자동으로 만족한다.

전체 루프

vector<int> matroidIntersection(int n) {
    vector<int> S;
    while (augment(S, n)) {}
    return S;
}

복잡도

• 증강 횟수: \(O(r)\), \(r = \min(r_1, r_2)\).
• 매 증강: 교환 그래프 구성에 \(O(r \cdot n)\)번 오라클 호출, 각 오라클 \(O(\gamma)\).
• 총 \(O(r^2 n \gamma)\). 가중치 없는 경우의 표준 복잡도.

오라클을 증분식으로 최적화하면 더 빨라진다(예: 그래프 매트로이드는 union-find 재사용).

가중치 버전(요약)

최대 가중치 공통 독립 집합은 BFS 대신 최단 경로(가중) + 동순위 시 간선 수 최소의 lexicographic 규칙으로 증강한다(Bellman-Ford류, 음수 가중 가능 → SPFA/Johnson). 각 크기에서의 최대 가중치를 모두 얻을 수 있다.

검증 예제: 이분 매칭

// 좌측 L, 우측 R. 원소 = 간선.
// M1: 각 좌측 정점에 간선 <= 1  (분할 매트로이드)
// M2: 각 우측 정점에 간선 <= 1  (분할 매트로이드)
// matroidIntersection 결과 크기 == 최대 매칭

홉크로프트-카프보다 느리지만, 교집합 코드가 옳음을 검증하는 안전한 테스트다.

함정

• 반드시 BFS(최단). DFS로 아무 경로나 쓰면 독립성이 깨진다.
• 오라클의 \(S - y + x\) 의미를 정확히: \(y\)를 빼고 \(x\)를 넣은 집합의 독립성.
• \(X_1 \cap X_2\)가 비어 있지 않으면 길이 0 경로(원소 하나 추가)로 즉시 증강.

매트로이드 교집합은 "단일 매트로이드로 안 되는 이중 제약 최적화"의 만능 틀이다.