Breaking Symmetries from a Set-Covering Perspective

1. 문제 정의 (Problem)

• 배경: 그래프 탐색 문제 (예: 램지 수 계산, 스도쿠 최소 힌트 문제 등) 는 정점의 순서를 바꾸더라도 동일한 구조 (동형, Isomorphic) 를 가지는 대칭적인 해가 매우 많습니다. 이로 인해 검색 공간이 기하급수적으로 커지고 불필요한 탐색이 발생합니다.
• 목표: 각 동형 클래스 (Isomorphism Class) 에서 하나의 '정규형 (Canonical)' 그래프만 선택하도록 검색 공간을 제한하는 것입니다.
• 기존 접근법의 한계:
  • 완전한 대칭성 깨기 (Complete Symmetry Break) 를 위해 모든 치환 (Permutation) 에 대한 제약 조건을 추가하면 제약 조건의 수가 지수적으로 증가하여 실용적이지 않습니다.
  • 기존 연구들은 주로 '어떤 치환 집합이 대칭성을 깨는가'에 초점을 맞췄으며, 최적의 치환 집합을 찾는 것은 NP-완전 문제로 알려져 있어 대규모 그래프 (n > 10) 에서는 적용이 어렵습니다.

2. 방법론 (Methodology)

저자들은 대칭성 깨기를 **집합 덮기 문제 (Set-Cover Problem)**로 재정의했습니다.

2.1. 집합 덮기 관점의 공식화

• 커버 (Cover): 치환 $\pi$가 그래프 $G$를 적용했을 때 $G$보다 작아지는 경우 ($\pi(G) < G$), $\pi$는 $G$를 '커버'한다고 정의합니다.
• 목표: 모든 '비정규형 (Non-canonical)' 그래프를 커버하는 최소 크기의 치환 집합을 찾는 것입니다. 이는 전형적인 집합 덮기 문제 (Universe: 비정규형 그래프, Subsets: 각 치환이 커버하는 그래프 집합) 와 동일합니다.
• 최적 Lex-Leader 대칭성 깨기: 최소 크기의 치환 집합을 찾는 것을 목표로 합니다.

2.2. 핵심 최적화 기법

직접적인 행렬 구성은 $n!$개의 치환과 $2^{n(n-1)/2}$개의 그래프로 인해 불가능하므로, 다음과 같은 세 가지 최적화 기법을 적용하여 문제를 축소합니다.

1. 치환 우세 (Permutation Dominance): 치환 $\pi_1$이 커버하는 그래프 집합이 $\pi_2$의 부분집합이면, $\pi_2$가 $\pi_1$을 우세한다고 정의합니다. 이 경우 $\pi_1$은 제거됩니다.
2. 그래프 우세 (Graph Dominance): 그래프 $G_1$을 커버하는 치환 집합이 $G_2$를 커버하는 치환 집합의 부분집합이면, $G_2$는 $G_1$에 의해 우세하다고 정의합니다. 이 경우 $G_2$는 제거됩니다.
3. 백본 (Backbone) 식별: 어떤 그래프를 오직 하나의 치환만이 커버할 때, 해당 치환은 '백본 (Backbone)'으로 간주되어 최적 해에 반드시 포함되어야 합니다. 이를 식별하면 해당 행과 열을 제거할 수 있습니다.

2.3. 심볼릭 표현 및 패턴 (Patterns)

• 패턴 (Patterns): 치환이 커버하는 그래프 집합은 $2^{n(n-1)/2}$개나 될 수 있으나, 이를 **패턴 (Pattern)**이라는 간결한 표현으로 요약할 수 있습니다. 패턴은 특정 인덱스에서 레xicographical 순서가 작아지는 조건을 만족하는 그래프들의 집합을 나타냅니다.
• SAT 기반 최적화: 행렬을 명시적으로 구성하기 전에, 패턴을 사용하여 치환 간의 우세 관계와 백본을 SAT (Satisfiability) 솔버를 통해 심볼릭하게 식별합니다. 이를 통해 대규모 문제를 다룰 수 있습니다.

2.4. 알고리즘 흐름

1. 백본 탐색: 그래프를 순회하거나 (Algorithm 3), 치환을 순회하여 (Algorithm 4) 필수적인 백본 치환들을 찾습니다.
2. 우세 제거: 백본을 기준으로 나머지 치환들 간의 우세 관계를 SAT 를 통해 반복적으로 제거합니다.
3. 최종 집합 덮기: 축소된 행렬에 대해 최적 집합 덮기 문제 (OPB, Optimization Pseudo-Boolean) 를 풀어 최종적인 최소 치환 집합을 도출합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 공식화: 대칭성 깨기를 집합 덮기 문제로 공식화하여, 기존 집합 덮기 분야의 정밀 및 근사 기법들을 적용할 수 있는 기반을 마련했습니다.
2. 최적 Lex-Leader 제약 조건 도출: $n \le 10$인 그래프에 대해 최소 개수의 Lex-제약 조건을 가진 완전한 대칭성 깨기 (Complete Symmetry Break) 를 최초로 계산했습니다.
3. 효율적인 축소 기법: 패턴 (Patterns) 과 SAT 기반의 심볼릭 연산을 통해 $n=10$과 같은 대규모 문제에서도 행렬을 구성하지 않고도 백본과 우세 관계를 식별하여 문제를 극도로 축소하는 방법을 제시했습니다.
4. 부분 대칭성 깨기 개선: 백본 치환 집합을 이용한 부분 대칭성 깨기가 기존 전치 (Transposition) 기반 방법보다 더 정밀하고 적은 수의 제약 조건으로 높은 성능을 보임을 입증했습니다.

4. 실험 결과 (Results)

• 성능: $n \le 10$인 그래프에 대해 최적의 대칭성 깨기를 성공적으로 계산했습니다.
  • $n < 10$의 경우, 일반 집합 덮기 솔버를 호출하기 전까지의 최적화 (백본 식별 및 우세 제거) 만으로 모든 문제가 해결되었습니다.
  • $n = 10$의 경우, 초기 행렬 크기 ($10! \times 2^{45}$) 가 199 행 $\times$ 197 열로 축소되었으며, 이를 OPB 솔버 (RoundingSat) 로 0.01 초 만에 해결했습니다.
• 비교: 기존 연구 [19] 에서 제안된 치환 집합 크기와 비교했을 때, 본 연구에서 찾은 최적 해는 약 10% 미만의 치환 수로 더 효율적입니다.
• 부분 대칭성 깨기: 백본 기반의 부분 대칭성 깨기는 전치 (Transposition) 기반 방법보다 중복 비율 (Redundancy Ratio) 이 훨씬 낮아 (더 정밀함) 더 우수한 성능을 보였습니다 (예: $n=10$에서 전치 45 개 대비 백본 131 개로 더 정밀한 제어).

5. 의의 및 결론 (Significance)

• 이론적 확장: 대칭성 깨기 문제를 집합 덮기 프레임워크로 통합함으로써, 수십 년간 연구된 집합 덮기 알고리즘 (정확 및 근사) 을 그래프 이론 문제에 직접 적용할 수 있는 새로운 길을 열었습니다.
• 실용적 가치: $n \le 10$까지의 그래프에 대해 최적의 대칭성 깨기 제약 조건을 생성할 수 있음을 입증하여, 조합적 탐색 문제의 해결 능력을 크게 향상시켰습니다.
• 향후 전망: 백본과 패턴 기반의 접근법은 완전한 대칭성 깨기뿐만 아니라, 작고 정밀한 **부분 대칭성 깨기 (Partial Symmetry Break)**를 구성하는 데에도 매우 효과적임을 보였습니다. 이는 대규모 그래프 문제에서도 실용적인 대칭성 제거 전략으로 활용될 수 있습니다.

요약하자면, 이 논문은 대칭성 깨기라는 난제를 집합 덮기 문제로 변환하고, 패턴 기반의 심볼릭 최적화 기법을 통해 기존에는 풀기 어려웠던 $n \le 10$ 규모의 그래프에 대해 최적의 대칭성 깨기 제약 조건을 찾아내는 데 성공했습니다.