imeimi / Algorithm DB

Matroid Intersection

1정의

두 매트로이드 M1 = (E, ℐ1), M2 = (E, ℐ2)의 교차(intersection) ℐ1 ∩ ℐ2는 일반적으로 매트로이드가 아니다. 매트로이드 교차 문제는 ℐ1 ∩ ℐ2에서 최대 크기 집합을 구하는 문제이다.

매트로이드 M = (E, ℐ)와 독립 집합 X ∈ ℐ에 대해 교환 그래프 DM(X)를 다음과 같이 정의한다.

DM(X) = (E, { (u, v) | u ∈ X, v ∈ E\X, (X\{u}) ∪ {v} ∈ ℐ })

M1, M2에 대해 교환 그래프 DM1,M2(X)는 DM1(X)의 간선과 DM2(X)의 방향을 뒤집은 간선을 합친 유향 이분 그래프이다.

2알고리즘

I = ∅에서 시작한다. 현재 I에 대해 집합 U, V를 다음과 같이 정의한다.

  • U = { x ∈ E\I : I ∪ {x} ∈ ℐ1 }
  • V = { x ∈ E\I : I ∪ {x} ∈ ℐ2 }

DM1,M2(I)에서 U의 정점에서 V의 정점으로 가는 최단 경로 R을 구한다. R이 존재하면 I를 I △ R으로 갱신하고, R이 존재하지 않으면 종료한다.

2.1보조 정리 1

이분 그래프 G = (X, Y, E)가 유일한 완전 매칭 M을 가지면, 다음을 만족하는 순열 X = {x1, ⋯, xn}, Y = {y1, ⋯, yn}이 존재한다.

{ (x1, y1), ⋯, (xn, yn) } ⊆ M, ∀1 ≤ i < j ≤ n: (xi, yj) ∉ E.

매칭 간선은 Y → X 방향, 나머지 간선은 X → Y 방향으로 방향을 붙이자. 이 유향 그래프에 사이클이 존재하면 사이클 위의 간선 방향을 뒤집어 다른 완전 매칭을 만들 수 있으므로 유일성에 모순이다. 따라서 DAG이고, 위상 정렬 순서 T를 붙일 수 있다. T(xi-1) > T(xi)가 되도록 번호를 붙이면 매칭 간선에 의해 T(xi) > T(yi)이다. (xi, yj) ∈ E이고 i < j이면 T(xj) < T(xi) < T(yj) < T(xj)가 되어 모순이다. ■

2.2보조 정리 2

A ∈ ℐ이고 B ⊆ E이며 |A| = |B|이고, DM(A)가 A △ B에서 유일한 완전 매칭을 가지면 B ∈ ℐ이다.

보조 정리 1에 의해 A\B = {x1, ⋯, xn}, B\A = {y1, ⋯, yn}으로 순열을 만들 수 있다.

B가 종속이라 가정하면 C ⊆ B인 회로 C가 존재하고, yi ∈ C인 i가 하나 이상 존재한다. 이러한 i 중 최솟값을 고르자.

C ⊆ B = (A ∩ B) ∪ {y1, ⋯, yn}이고 i가 최솟값이므로 j < i이면 yj ∉ C이다. 따라서 C\{yi}의 원소는 A ∩ B에 속하거나 yj (j > i)이다.

이 원소들이 모두 span(A\{xi})에 속함을 보인다. xi ∈ A\B이므로 A ∩ B ⊆ A\{xi}이고, A\{xi} ⊆ span(A\{xi})이다. j > i이면 보조 정리 1의 조건 (xi, yj) ∉ E에 의해 (A\{xi}) ∪ {yj} ∉ ℐ이다. A ∈ ℐ이므로 A\{xi} ∈ ℐ이고, 여기에 yj를 추가해도 독립이 아니므로 r((A\{xi}) ∪ {yj}) = r(A\{xi})이다. 따라서 yj ∈ span(A\{xi})이다. 따라서 C\{yi} ⊆ span(A\{xi})이다.

C\{yi} ⊆ span(A\{xi})이고 span(span(A\{xi})) = span(A\{xi})이므로 단조성에 의해 span(C\{yi}) ⊆ span(A\{xi})이다. C는 회로이므로 yi ∈ span(C\{yi}) ⊆ span(A\{xi})이다. 그런데 A ∈ ℐ이므로 A\{xi} ∈ ℐ이고 r(A\{xi}) = |A| - 1이다. (xi, yi)가 DM(A)의 매칭 간선이므로 (A\{xi}) ∪ {yi} ∈ ℐ이고 r((A\{xi}) ∪ {yi}) = |A|이다. 이는 yi ∉ span(A\{xi})라는 의미이므로 모순이고, B ∈ ℐ이다. ■

2.3보조 정리 3

R이 존재하면 J = I △ R ∈ ℐ1 ∩ ℐ2이고 |J| = |I| + 1이다.

WLOG J ∈ ℐ1을 보인다.

R = y0, x1, ⋯, xn, yn으로 두면 xi ∈ I, yi ∉ I이므로 |J| = |I| + 1이다. J = {y0, ⋯, yn} ∪ (I\{x1, ⋯, xn})이다.

A = {y1, ⋯, yn} ∪ (I\{x1, ⋯, xn})으로 두자. 간선 (xi, yj) (i < j)가 존재하면 R보다 짧은 증가 경로가 존재하여 R이 최단 경로인 것에 모순이므로 (xi, yi)는 DM1(A)에서 A △ I에 대한 유일한 완전 매칭이고, 보조 정리 2에 의해 A ∈ ℐ1이다.

i ≥ 1에 대해 yi ∉ U이므로 I ∪ {yi} ∉ ℐ1이고, I ∈ ℐ1이므로 yi ∈ span1(I)이다. 따라서 {y1, ⋯, yn} ⊆ span1(I)이고, 단조성과 span1(span1(I)) = span1(I)에 의해 span1(I ∪ A) ⊆ span1(span1(I)) = span1(I)이므로 r1(I ∪ A) = r1(I) = |I|이다. |A| = |I| − n + n = |I|이므로 r1(I ∪ A) = |I| = |A|이다. I ∪ {y0} ∈ ℐ1이고 |I| = |A|이므로 (I3)에 의해 a ∈ (I ∪ {y0})\A인 a가 존재하여 A ∪ {a} ∈ ℐ1이다. a ∈ I이면 r1(I ∪ A) ≥ |A| + 1이 되어 모순이므로 a = y0이다. 따라서 J = A ∪ {y0} ∈ ℐ1이다. ■

보조 정리 3에 의해 알고리즘은 I ∈ ℐ1 ∩ ℐ2를 유지한다.

3Min-Max 정리

maxX ∈ ℐ1 ∩ ℐ2(|X|) = minX ⊆ E(r1(X) + r2(E\X)).

3.1보조 정리 4

maxX ∈ ℐ1 ∩ ℐ2(|X|) ≤ minX ⊆ E(r1(X) + r2(E\X)).

임의의 A ∈ ℐ1 ∩ ℐ2, B ⊆ E를 고르자. A ∩ B ⊆ A ∈ ℐ1이므로 (I2)에 의해 A ∩ B ∈ ℐ1이다. A ∩ B ⊆ B이므로 |A ∩ B| ≤ r1(B)이다. 마찬가지로 A\B ⊆ A ∈ ℐ2이므로 A\B ∈ ℐ2이고, A\B ⊆ E\B이므로 |A\B| ≤ r2(E\B)이다. 따라서 |A| = |A ∩ B| + |A\B| ≤ r1(B) + r2(E\B)이다. ■

3.2보조 정리 5

R이 존재하지 않으면 |I| = minX ⊆ E(r1(X) + r2(E\X))이다.

U = ∅이면 I가 M1의 베이스이므로 r1(E) = |I|이다. X = E를 대입하면 r1(E) + r2(∅) = |I|이므로 minX ⊆ E(r1(X) + r2(E\X)) ≤ |I|이고, 보조 정리 4에 의해 등호가 성립한다. WLOG V = ∅이면 minX ⊆ E(r1(X) + r2(E\X)) = |I|.

둘 모두 공집합이 아닐 때 X를 DM1,M2(I)에서 V로 가는 경로가 존재하는 정점의 집합으로 정의하면 U ∩ X = ∅이고 X ⊆ V이다.

r1(X) > |I ∩ X|라 가정하면 ∃ x ∈ X\I s.t. (I ∩ X) ∪ {x} ∈ ℐ1이다. x ∈ X이므로 x ∉ U, 즉 I ∪ {x} ∉ ℐ1이다. I가 독립이므로 I ∪ {x}에는 x를 포함하는 기본 회로 C1이 유일하게 존재한다. (I ∩ X) ∪ {x} ∈ ℐ1이므로 C1 ⊄ (I ∩ X) ∪ {x}이고, C1 ⊆ I ∪ {x}이므로 ∃ y ∈ C1 ∩ (I\X)이다. C1이 유일한 회로이므로 (I ∪ {x})\{y} ∈ ℐ1이다. 그러면 간선 (y, x)가 DM1,M2(I)에 존재하고, y ∉ X임에도 y에서 V로 가는 경로가 존재하므로 모순이다. 따라서 r1(X) ≤ |I ∩ X|이다.

WLOG r2(E\X) ≤ |I\X|이다.

보조 정리 4에 의해 r1(X) + r2(E\X) ≤ |I ∩ X| + |I\X| = |I| ≤ r1(X) + r2(E\X)이므로 등호가 성립한다. ■

보조 정리 4와 5에 의해 Min-Max 정리가 성립하며, 보조 정리 5에 의해 알고리즘은 ℐ1 ∩ ℐ2에서 최대 크기 집합을 구한다.

4NP-Completeness

3개 이상의 매트로이드에 대한 공통 독립 집합 결정 문제는 NP-Complete이다.

유향 그래프 G = (V, E)에서 ℐ1 = { F ⊆ E : 모든 정점의 in-degree ≤ 1 }, ℐ2 = { F ⊆ E : 모든 정점의 out-degree ≤ 1 }, ℐ3 = { F ⊆ E : 방향을 무시하면 forest }로 정의하면 (E, ℐ1), (E, ℐ2), (E, ℐ3)의 교차에서 크기 |V| - 1인 집합을 찾는 것은 해밀턴 경로 문제와 동치이고, 이는 NP-Complete 문제이다. ■