주어진 둘레를 가진 새로운 작은 정규 그래프: 케이지 문제와 그 이상

기본 정보

• 논문 ID: 2511.07247
• 제목: New small regular graphs of given girth: the cage problem and beyond
• 저자: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• 분류: math.CO (조합론), cs.DM (이산수학)
• 발표 시간: 2025년 11월 11일
• 논문 링크: https://arxiv.org/abs/2511.07247

초록

케이지 문제(cage problem)는 최소 정점 수를 가진 $(k,g)$-그래프, 즉 $k$-정규 그래프이면서 둘레(girth)가 $g$인 그래프를 찾는 것에 관한 문제입니다. 핵심 목표는 $n(k,g)$(이러한 그래프의 최소 차수)를 결정하고 해당하는 극값 그래프를 식별하는 것입니다. 본 논문은 계산 관점에서 케이지 문제 및 그 여러 변형을 연구하며, 네 가지 상호 보완적인 그래프 생성 알고리즘을 개발했습니다: 리프트(lifts) 기반 완전 탐색, 금지 탐색(tabu search) 휴리스틱, 산악 등반(hill climbing) 휴리스틱 및 절단 기법. 이러한 방법들을 활용하여 고전 케이지 문제의 11개 경우에 대한 새로운 상한을 설정했습니다: $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$, $n(14,7) \leq 4716$. 이러한 결과는 22년간 유지되어온 여러 최적 알려진 상한을 개선했으며, 특히 $n(4,10)$을 384에서 320으로 낮춘 것은 실질적인 개선입니다.

연구 배경 및 동기

문제 정의

1. 핵심 문제: 케이지 문제는 최소 정점 수 $n(k,g)$를 가진 $k$-정규 그래프이면서 둘레가 $g$인 $(k,g)$-케이지를 찾습니다. 둘레는 그래프에서 가장 짧은 사이클의 길이입니다.
2. 문제의 중요성:
   • 이론적 의의: 케이지는 극값 그래프 이론의 중심 연구 대상이며, Moore 한계 등 고전 이론과 밀접한 관련이 있습니다
   • 실제 응용: 희소하고 고도로 대칭적인 구조는 통신 네트워크 설계, 오류 정정 코드, 암호학 등의 분야에서 응용 가치를 가집니다
   • 네트워크 설계: 효율적인 균일한 정보 전파를 지원하고, 중심 노드의 과부하를 피하며, 장애에 대한 견고성을 제공하는 위상 구조를 제공합니다
3. 기존 방법의 한계:
   • 대부분의 매개변수 쌍 $(k,g)$에 대해 정확한 값 $n(k,g)$는 미지수입니다
   • 기존 상한은 여러 해 동안 개선되지 않았습니다(일부 상한은 22년 유지)
   • Moore 그래프는 $g \in \{3,4,5,6,8,12\}$일 때만 존재할 수 있습니다
   • 계산 복잡도는 $k$와 $g$의 증가에 따라 급격히 증가합니다
4. 연구 동기:
   • 현대 계산 능력과 최적화 알고리즘을 활용하여 장기간 유지된 상한 개선
   • 케이지 문제 및 그 변형을 처리하기 위한 체계적인 계산 방법 개발
   • 구체적인 그래프 인스턴스 구성을 통해 이론 연구에 증거 제공(예: 짝수 둘레 케이지의 이분성 추측)

핵심 기여

1. 알고리즘 프레임워크: 네 가지 상호 보완적인 그래프 생성 알고리즘 개발
   • 전압 그래프 리프트 기반 백트래킹 알고리즘(BTA)
   • 금지 탐색 휴리스틱(TS)
   • 산악 등반 휴리스틱
   • 절단 기법
2. 고전 케이지 문제의 돌파: 11개의 새로운 상한 설정, 포함:
   • $n(4,10) \leq 320$ (384에서 대폭 감소)
   • $n(3,16) \leq 936$ (960에서 개선)
   • $n(3,17) \leq 2048$ (2176에서 개선)
   • $n(4,11)$과 $n(6,11)$에 대한 첫 번째 비자명 상한 제공
3. 변형 문제의 진전:
   • 간선 둘레 정규(egr) 그래프: 21개의 새로운 상한 (2개의 타이트 상한)
   • 정점 둘레 정규(vgr) 그래프: 29개의 새로운 상한 (7개의 타이트 상한)
   • $(k,g,g+1)$-그래프: 6개의 새로운 상한
   • $(k,g)$-스펙트럼: 34개의 이전에 미해결된 차수 결정
4. 계산 자원 및 재현성:
   • 약 5 CPU년의 계산 작업
   • 모든 코드 및 데이터는 GitHub에 공개
   • 완전한 검증 및 건전성 검사 제공

방법 상세 설명

작업 정의

입력: 정규 차수 $k$, 둘레 $g$, 선택적 추가 제약(예: 정점/간선 둘레 정규성)

출력: 조건을 만족하는 최소 차수 그래프 또는 개선된 상한 $n(k,g)$

제약: 그래프는 $k$-정규(각 정점의 차수가 $k$)이고 둘레가 최소 $g$(최단 사이클 길이 $\geq g$)이어야 합니다

핵심 기술: 전압 그래프 리프트(Voltage Graph Lifts)

기본 원리

기본 그래프 $G=(V,E)$, 군 $\Gamma$ 및 전압 할당 $\alpha: A \rightarrow \Gamma$ (여기서 $A$는 방향 간선 집합)이 주어지면, 리프트 그래프 $G_\alpha$의 정점 집합은: $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

각 호(arc) $(u,v) \in A$와 각 $s \in \Gamma$에 대해, 호 $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$가 존재합니다.

주요 성질

1. 정규성 보존(관찰 1): $G$가 $k$-정규 ⟺ $G_\alpha$가 $k$-정규
2. 연결성 필요 조건(관찰 2): $G$가 비연결이면 $G_\alpha$도 비연결
3. 둘레 계산(명제 1): $G_\alpha$의 둘레는 $G$의 방향 그래프에서 최단 폐쇄 비반전 경로(순 전압이 $0_\Gamma$)의 길이와 같습니다
4. 생성 트리 단순화(명제 2): 생성 트리의 모든 간선에 전압 $0_\Gamma$를 할당해도 리프트 그래프의 동형류는 변하지 않습니다

알고리즘 1: 백트래킹 알고리즘(BTA)

구조화된 배제 규칙

구조 기반 배제(전압 할당과 무관):

1. 반간선 제약: 반간선에 해당하는 호는 2차 군 원소만 할당 가능
2. 생성 트리 최적화: 생성 트리 $T$를 선택하고, 그 간선의 전압을 $0_\Gamma$로 설정
3. 사이클 기반 배제: 비트리 간선의 경우, 전압 $a$를 할당하면 길이 $(q+1)s$ (여기서 $a^s=0_\Gamma$)이고 목표 둘레보다 작은 사이클이 생성되면 해당 전압을 배제

할당 기반 배제(부분 전압 할당에 따라):

1. 규범성 검사(알고리즘 1):
   • 군 자동동형 $\phi_\Gamma$와 간선 자동동형 $\phi_G$ 활용
   • 사전식 최소 대표원만 보존
   • 부분 할당이 규범적이지 않으면 모든 완성을 배제 가능
2. 증분 둘레 검증(알고리즘 2):
   • 새 할당 간선을 사용하는 폐쇄 비반전 경로만 검사
   • 증분 성질을 활용하여 효율성 향상

알고리즘 흐름(알고리즘 3)

BTA(G, Γ, g_min):
  1. 구조 검사 수행, 가능한 전압 집합 N 결정
  2. 전압 재귀적 할당:
     - 각 유용한 호 d에 대해 N(d)의 각 전압 시도
     - 둘레 검사 및 규범성 검사 적용
     - 통과하면 다음 호 재귀 처리
     - 백트래킹 시 상태 복원
  3. 완전 할당 후 리프트 그래프 구성 및 필터링

알고리즘 2: 금지 탐색(TS)

동기

BTA는 대규모 인스턴스에서 계산 오버헤드가 크므로, TS는 휴리스틱 샘플링을 통해 유망한 전압 할당을 탐색합니다.

주요 구성 요소

이웃 정의: 정확히 한 간선에 해당하는 군 원소를 변경하는 모든 대체 할당

비용 함수:

1. 둘레 기반($c_{girth}$): $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{if } \text{Ord}(a) \neq 1 \\ C & \text{otherwise} \end{cases}$ 여기서 $C$는 큰 페널티 상수, $m$은 샘플 경로 수
2. 정규성 기반($c_{reg}$): $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ 여기서 $f_V$와 $f_D$는 각각 정점과 호가 둘레 사이클에서 나타나는 빈도

금지 리스트: 최근 수정 작업을 저장하여 즉시 복귀 방지, 길이는 $3|\Gamma|$

교란 메커니즘: 국소 최적에 갇혔을 때 무작위 수정 적용하여 탈출

하이퍼파라미터 설정(표 1)

• 간선/군 자동동형 수 제한: 200/2000
• BTA 및 TS 시간 제한: 각 20초/인스턴스
• 이웃 최소 둘레: $g_{nbr} = g_{min} - 2$ (둘레 문제) 또는 $g_{nbr} = g_{min}$ (정규성 문제)

알고리즘 3: 산악 등반 휴리스틱

이전 방법과의 차이점: 기본 그래프와 전압 할당을 동시에 탐색

흐름:

1. $n$개의 고립 정점에서 시작
2. 각 반복:
   • 추가 가능한 모든 호 쌍과 전압 할당 $t \in T(G)$ 고려
   • $|T(G_t)|$를 최대화하는 수정 선택 (탐욕 전략)
3. 리프트 그래프가 기록을 깨는지 확인

알고리즘 4: 절단 기법

기본 아이디어: 알려진 작은 $(k,g+1)$-그래프에서 정점을 삭제한 후 간선을 추가하여 $k$-정규로 완성

구체적 전략:

1. 둘레 7, 짝수 차수 $8 \leq k \leq 14$:
   • $(k,8)$-케이지에서 거리 4인 두 정점 $u,v$ 삭제
   • $N_1(u), N_1(v), N_2(u,v)$ 삭제
   • 절단 집합 크기: $3k$ (de Ruiter와 Biggs의 $3k-1$에서 개선)
2. 둘레 11:
   • $(4,12)$-케이지에서: 거리 6인 $u,v$ 삭제, $N_1(u), N_1(v), N_3(u,v)$ 및 $N_2(u) \cap N_4(v)$의 한 정점 삭제, $3k+3$개 정점 절단
   • $(6,12)$-케이지에서: 유사 전략, $5k-1$개 정점 절단

실험 설정

계산 자원

• 총 계산량: 약 5 CPU년
• 기반 시설: Flemish Supercomputer Center (VSC)
• 구현 언어: C++ 기반 (추정, 명시적 설명 없음)

기본 그래프 및 군 생성

1. 군: GAP 시스템을 사용하여 모든 차수 $n < 1024$의 비동형 군 생성
2. 기본 그래프:
   • multigraph 생성기 확장 (multigraph+)
   • 평행 간선, 루프 및 반간선을 포함하는 연결 정규 그래프 생성
   • Nauty를 사용하여 동형 그래프 제거

검증 전략

1. 입력 검증:
   • 군: GAP에서 직접 획득
   • 기본 그래프: pregraph 생성기와 비교 (차수 13까지)
2. 최적화 정확성:
   • 각 최적화 개별 비활성화 (그래프 자동동형, 군 자동동형, 둘레 한계)
   • 생성된 비동형 리프트 그래프 수 일치 확인
3. 완전성 검증:
   • 세 개의 독립적 구현과 비교:
     • $K_{1,3}$ 기본 구성
     • Gray 및 Theta 그래프 리프트
     • 블록 순환 그래프 생성기 (순환 군 리프트와 동등)
   • 모든 경우 출력 완전 일치

필터링 흐름

1. 연결성 검사
2. 동형 필터링: Nauty를 사용하여 규범 표현 구성
3. 둘레 및 정규성 검증: 29의 알고리즘 사용

실험 결과

주요 결과: 고전 케이지 문제(표 2)

주목할 만한 개선

절단 기법 성과

• $(8,7) \leq 774$ (777에서 3개 정점 개선)
• $(10,7) \leq 1608$ (1611에서 3개 정점 개선)
• $(12,7) \leq 2890$ (2893에서 3개 정점 개선)
• $(14,7) \leq 4716$ (4719에서 3개 정점 개선)

주요 발견

1. $(4,10)$의 돌파: 384에서 320으로 감소, 감소율 16.7%, 가장 놀라운 개선
2. 이분성 증거: 새로운 $(3,16)$과 $(4,10)$ 그래프 모두 이분 그래프, "짝수 둘레 케이지는 이분 그래프"라는 추측 지지
3. 구성 세부사항(그림 4):
   • $(3,16)$: 군 $C_{13} \rtimes C_9$ (차수 117) 사용, 기본 그래프 8개 정점
   • $(4,10)$: 군 $C_5 \times D_4$ (차수 40) 사용, 기본 그래프 8개 정점

변형 문제 성과

간선 둘레 정규 그래프(표 3)

• 21개의 새로운 상한, 그 중 2개의 타이트 상한 (상한과 하한 동일):
  • $n(4,5,4) = 30$ (새로 결정)
  • 여러 $(6,5,\lambda_e)$ 경우 처음으로 상한 획득

정점 둘레 정규 그래프(표 4)

• 29개의 새로운 상한, 그 중 7개의 타이트 상한:
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • 여러 $(4,6,\lambda_v)$ 경우 대폭 개선

$(k,g)$-스펙트럼(표 5)

• 34개의 이전에 미해결된 차수 결정
• 주로 집중:
  • $(3,11)$과 $(3,12)$: 7개의 새로운 차수
  • $(4,7)$과 $(4,8)$: 12개의 새로운 차수
  • $(5,7)$: 24개의 새로운 차수 (184에서 256)

무$(g+1)$-사이클 그래프(표 6)

• 6개의 새로운 상한:
  • $n(3,11,12) \leq 228$ (272에서 개선)
  • $n(3,13,14) \leq 600$ (800에서 개선)
  • $n(3,15,16) \leq 1760$ (2162에서 개선)

알고리즘 효율성 분석

시간 할당 전략

• 각 기본 그래프-군 조합: BTA 20초, TS 20초
• TS 초기 해 탐색: 2초
• 그래프 자동동형 탐색: 2초

알고리즘 상호 보완성

1. BTA: 작은 인스턴스 완전 탐색, 완전성 보장
2. TS: 큰 인스턴스 휴리스틱 샘플링, 확장성 우수
3. 산악 등반: 기본 그래프와 할당 동시 최적화, 유연성 높음
4. 절단: 알려진 큰 그래프 활용, 목표 지향성 강함

관련 연구

고전 케이지 문제 연구

1. 이론적 한계:
   • Moore 한계 (1963): 기본 하한
   • Sauer (1967): $n(k,g) < n(k,g+1)$ 부등식
   • Wong (1982): 케이지 종합 조사
2. 구성 방법:
   • Balaban (1972-1973): $(3,10)$과 $(3,11)$ 케이지
   • Benson (1966): $(k,12)$ 케이지
   • Biggs 일련 연구: 여러 작은 둘레 그래프
3. 계산 방법:
   • McKay 등 (1998): 케이지용 빠른 백트래킹
   • Exoo (2002-2020): 전압 그래프 기법
   • de Ruiter & Biggs (2015): 정수 계획법 및 절단

리프트 이론

• Gross & Tucker (1987): 위상 그래프 이론 기초
• Exoo & Jajcay (2011): 전압 그래프 리프트의 둘레 이론
• 본 논문: 체계적 최적화 및 휴리스틱 방법 확장

변형 문제

1. 둘레 정규 그래프:
   • Jajcay 등 (2018): 간선 둘레 정규 그래프
   • Jajcay 등 (2024): 정점 둘레 정규 그래프
   • Goedgebeur & Jooken (2025): 완전 탐색 생성
2. 스펙트럼 문제:
   • Eze 등 (2025): $(k,g)$-스펙트럼의 이론 및 계산 방법
3. 무 짧은 사이클 그래프:
   • Eze 등 (2026): $(k,g,g+1)$-그래프 및 케이지 문제와의 연관성

본 논문의 장점

1. 체계적 프레임워크: 케이지 문제 및 여러 변형 통일 처리
2. 알고리즘 상호 보완: 네 가지 방법이 다양한 규모와 특성 커버
3. 실질적 개선: 여러 장기 기록 돌파
4. 개방 자원: 코드 및 데이터 완전 공개

결론 및 논의

주요 결론

1. 고전 케이지 문제 돌파:
   • 11개의 새로운 상한, 그 중 $(4,10)$ 개선이 가장 두드러짐 (384→320)
   • 일부 상한 22년 만에 처음 개선
   • $(4,11)$과 $(6,11)$에 대한 첫 비자명 상한 제공
2. 변형 문제 진전:
   • 간선/정점 둘레 정규 그래프: 50개의 새로운 상한 (9개의 타이트 상한)
   • $(k,g)$-스펙트럼: 34개의 새로 결정된 차수
   • 무 $(g+1)$-사이클 그래프: 6개의 개선된 상한
3. 방법론 기여:
   • 리프트 기반 체계적 알고리즘 프레임워크
   • 구조화된 및 할당 기반 배제 규칙
   • 휴리스틱과 완전 탐색 방법의 효과적 결합

한계

1. 계산 복잡도:
   • 큰 $(k,g)$ 매개변수는 여전히 처리 어려움
   • 대량 계산 자원 필요 (5 CPU년)
   • 휴리스틱 방법은 최적해 발견 보장 안 함
2. 방법 적용 범위:
   • 리프트 방법은 적절한 기본 그래프와 군 존재에 의존
   • 절단 기법은 알려진 큰 그래프를 시작점으로 필요
   • 특정 매개변수 조합은 개선 미달성 (예: $(3,9)$, $(4,7)$ 등 알려진 케이지)
3. 이론적 간극:
   • 대부분 경우 상한과 하한 간격 여전히 큼
   • 새로운 하한 개선 미제공
   • 일부 매개변수에 대해 상한 여전히 "?" (미지수)로 표시
4. 하이퍼파라미터 민감성:
   • 시간 제한, 금지 리스트 크기 등 경험적 조정 필요
   • 체계적 하이퍼파라미터 최적화 연구 부재

향후 방향

1. 이론적 방향:
   • 새로운 구성된 그래프에서 무한족 유도
   • Moore 한계 및 그 변형 개선
   • 짝수 둘레 케이지의 이분성 추측 증명 또는 반박
2. 알고리즘 개선:
   • 더 효율적인 둘레 계산 알고리즘 개발
   • 기계 학습 보조 휴리스틱 설계 탐색
   • 현대 다중 코어 아키텍처 활용 병렬화
3. 절단 기법 일반화:
   • 절단 집합 선택 전략 체계화
   • 더 많은 $(k,g)$ 매개변수 쌍으로 확대
   • 절단 방법의 효과성에 대한 이론적 분석
4. 응용 탐색:
   • 새로 발견된 그래프를 네트워크 설계에 응용
   • 오류 정정 코드에서의 응용 탐색
   • 암호학 관련 성질 연구

심층 평가

장점

1. 중대한 실증적 기여:
   • 22년간 유지된 여러 기록 돌파, 특히 $(4,10)$의 대폭 개선
   • 다량의 구체적 구성 제공, 이론 연구에 소재 제공
   • 특정 매개변수에 대한 첫 비자명 상한 제공
2. 방법론 혁신:
   • 체계적 배제 규칙: 구조식 및 할당식 배제가 탐색 공간 대폭 감소
   • 알고리즘 상호 보완성: BTA, TS, 산악 등반 및 절단이 다양한 시나리오 커버
   • 증분 검증: 알고리즘 2의 증분 둘레 검사가 효율성 향상
   • 규범성 검사: 대칭성 활용하여 중복 계산 회피
3. 엄격한 실험 설계:
   • 다층 검증 전략 (입력, 최적화, 완전성)
   • 세 개의 독립적 구현과 비교
   • 상세한 하이퍼파라미터 설정 설명
   • 완전한 재현성 지원
4. 연구 광범위성:
   • 고전 문제뿐만 아니라 네 가지 변형 체계적 연구
   • 여러 변형에 대한 첫 상한 설정
   • 통일된 프레임워크로 다양한 문제 처리
5. 개방 과학 실천:
   • 코드 및 데이터 완전 공개 (GitHub)
   • 그래프 House of Graphs 데이터베이스 수록
   • 검증 가능한 증명서 제공 (구성된 그래프)

부족한 점

1. 제한된 이론적 깊이:
   • 주로 계산/실증 연구, 깊은 이론적 통찰 부족
   • 새로운 하한 또는 이론적 분석 미제공
   • 특정 매개변수 개선이 두드러진 이유에 대한 이론적 설명 부족
2. 방법 완전성:
   • 휴리스틱 방법 (TS, 산악 등반)은 완전성 보장 없음
   • 하이퍼파라미터 선택은 경험에 의존, 체계적 연구 부재
   • 다양한 알고리즘의 이론적 보장 또는 수렴성 분석 미흡
3. 실험 보고 세부사항:
   • 각 알고리즘이 특정 개선에 기여한 정도 미보고
   • 실행 시간의 상세 분석 부족
   • 실패 사례 또는 어려운 인스턴스에 대한 논의 미흡
4. 확장성 문제:
   • 더 큰 $k$와 $g$에 대한 방법 실행 가능성 불명확
   • 계산 자원 필요량이 매개변수 증가에 따라 어떻게 변하는지 분석 미흡
   • 일부 결과는 "≥100"으로 표시되어 완전 탐색 미실시 시사
5. 작문 조직:
   • 기술 세부사항 밀집, 비전문가에게 가독성 도전
   • 일부 알고리즘 설명 (예: 알고리즘 4 의사코드 부재) 불완전
   • 결과 표 다수이나 통합 요약 분석 부족

영향력

1. 학술적 영향:
   • 높음: 케이지 문제는 고전 극값 그래프 이론 문제, 장기 기록 개선은 중요한 의의
   • 57-Moore 그래프 등 유명한 미해결 문제에 간접적 연구 경로 제공
   • 방법은 다른 극값 그래프 문제로 확대 가능
2. 실용적 가치:
   • 중간: 새 그래프는 네트워크 위상 설계, 오류 정정 코드에 활용 가능
   • 오픈 소스 도구는 다른 연구자 사용 가능
   • 알고리즘 프레임워크는 관련 조합 최적화 문제에 적용 가능
3. 재현성:
   • 우수: 완전한 코드 및 데이터 공개
   • 상세한 검증 전략이 신뢰성 증강
   • 구체적 구성은 독립적 검증 가능
4. 후속 연구 잠재력:
   • 새 구성이 무한족 발견 영감 가능
   • 알고리즘 프레임워크는 다른 그래프 생성 문제에 적용 가능
   • 변형 문제의 첫 결과는 새 연구 방향 개척

적용 시나리오

1. 직접 응용:
   • 작은 고둘레 정규 그래프가 필요한 네트워크 설계
   • LDPC 코드 등 오류 정정 코드 구성
   • 키 공유 등 암호학 응용
2. 연구 도구:
   • 극값 그래프 이론의 계산 실험
   • 그래프 동형 및 규범화 알고리즘 테스트
   • 조합 최적화 휴리스틱의 벤치마크 테스트
3. 교육 자료:
   • 순수 수학에서 계산 방법 응용 시연
   • 알고리즘 설계 및 최적화의 사례 연구
   • 개방 과학 및 재현 연구의 범례
4. 확대 분야:
   • 다른 극값 그래프 문제 (Ramsey 수, Turán 문제 등)
   • 제약 만족 문제
   • 조합 설계 및 부호 이론

참고문헌 (정선)

1. 기초 이론:
   • 45 Sachs (1963): 모든 $k \geq 2, g \geq 3$에 대해 $(k,g)$-그래프 존재 증명
   • 31 Gross & Tucker (1987): 위상 그래프 이론 및 리프트 이론
   • 47 Wong (1982): 케이지 종합 조사
2. 계산 방법:
   • 24 Exoo 등 (2011): $(3,11)$과 $(4,7)$ 케이지의 계산 결정
   • 38 McKay 등 (1998): 빠른 백트래킹 원리
   • 15 de Ruiter & Biggs (2015): 정수 계획법
3. 최신 진전:
   • 22 Exoo & Jajcay (2011): 전압 그래프 리프트의 둘레 이론
   • 29 Goedgebeur & Jooken (2025): 간선 둘레 정규 그래프의 완전 탐색 생성
   • 34 Jajcay 등 (2024): 정점 둘레 정규 그래프
4. 도구:
   • 37 McKay & Piperno (2014): Nauty 그래프 동형 소프트웨어
   • 27 GAP 시스템: 군론 계산
   • 12 House of Graphs: 그래프 데이터베이스

종합 평가: 이는 체계적인 알고리즘 개발과 대규모 계산 실험을 통해 고전 케이지 문제 및 그 변형에서 현저한 실증적 진전을 이룬 고품질의 계산 조합론 논문입니다. 방법론상 혁신 (특히 배제 규칙 및 알고리즘 상호 보완성)과 엄격한 검증 전략이 주요 강점입니다. 이론적 깊이는 제한적이지만, 실증적 기여, 개방 과학 실천 및 분야에 대한 추진력이 이를 보완합니다. 극값 그래프 이론, 그래프 알고리즘 또는 조합 최적화를 연구하는 연구자에게 본 논문은 귀중한 방법론과 자원을 제공합니다.