그래프가 스스로를 위조하지 못할 때 — 모나딕 의존성은 왜 병합 폭을 묶는가

2025년 STOC에서 한 추측이 발표되고, 2026년 11월 4일 arXiv에 그 추측을 닫는 증명이 올라왔다. 그 사이 약 1년. 논문의 제목은 「Monadically Dependent Graph Classes Have Almost Bounded Merge-Width」이고, 저자는 Jan Dreier, Nikolas Mählmann, Michał Pilipczuk, Szymon Toruńczyk 네 명이다. 추측을 낸 사람은 이 논문의 첫 저자와 마지막 저자 — 즉 자기 추측을 자기가 닫은 셈이다.

이 글의 질문은 하나다. 그래프가 “자기 자신을 1차 논리로 흉내 낼 수 없을 만큼” 규칙적이라면, 그 그래프를 작은 조각으로 쪼개는 비용도 함께 작아지는가. 직관적으로는 그럴 것 같지만, 그 직관을 정리로 바꾸는 일은 20년 넘게 부분적으로만 성공해 왔다. 이 논문은 그 빈칸 하나를 “거의(almost)”라는 단어를 붙여 채운다.

1. “모나딕 의존성”은 무엇을 금지하는가

논문의 정의를 그대로 옮기면 이렇다. 그래프 클래스 C가 모나딕 의존적(monadically dependent)이라는 것은, C에 속한 정점 색칠 그래프들로부터 고정된 하나의 1차 논리(first-order logic) 공식만으로 모든 그래프를 해석(interpret)해 낼 수 없다는 뜻이다. 여기서 “해석”은 단순한 비유가 아니다. 원본 구조의 원소들을 몇 개의 공식으로 골라내고, 그 위에 관계를 다시 정의해서, 전혀 다른 구조를 그 안에 복제해 넣는 모델 이론의 정식 절차다.

따라서 이 정의는 “표현력의 상한”을 말한다. 색칠만 조금 바꿔 가며 임의의 그래프를 전부 흉내 낼 수 있는 클래스는 모나딕 의존적이 아니다. 반대로 아무리 커도 그런 위조가 불가능한 클래스는 모나딕 의존적이다. 이 조건은 단순히 “희소한 그래프”보다 넓다. 격자나 나무처럼 느슨한 구조뿐 아니라, 국소적으로는 상당히 빽빽한 구조까지 포함할 수 있는 넓은 우산이다.

문제는 이 정의가 아주 추상적이라는 점이다. “위조할 수 없다”는 성질만으로는 알고리즘을 설계할 수 없다. 계산기가 붙잡을 수 있는 형태 — 이를테면 그래프를 잘게 쪼개는 순서 — 로 번역해 주는 정리가 필요하다. 이것이 이 분야가 계속 파고든 지점이다.

2. 핵심 주장: 병합 폭은 거의 유계다

논문이 증명한 정리는 한 문장이다. 모든 모나딕 의존적 그래프 클래스는 거의 유계인 병합 폭(almost bounded merge-width)을 가진다. 병합 폭은 그래프를 “병합 열(merge sequence)”이라는 일련의 조작으로 재구성할 때 각 단계가 들고 있어야 하는 정보의 양을 재는 척도다. 논문은 이 병합 열이 바로 그 분해의 증인(witness)이 된다고 말한다.

왜 이 정리가 중요한가. 폭(width) 척도는 그래프 알고리즘의 통화 같은 것이다. 폭이 작으면 그래프를 작은 경계만 남기고 쪼갤 수 있고, 그러면 동적 계획법이 통한다. 트리 폭이 대표적이며, 클리크 폭은 그보다 넓은 클래스를 잡는다. 병합 폭은 이 계열에서 더 넓은 쪽에 서면서도 계산 가능한 분해를 주도록 설계된 척도다.

클리크 폭 구성을 도식화한 그림. 그래프를 만들어 가는 각 단계에서 유지해야 하는 색(정보)의 수가 폭이 된다 — David Eppstein, Public domain (Wikimedia Commons)

즉 이 정리는 “1차 논리로 통제 불가능한 클래스”라는 순수하게 논리적인 성질이, “작은 경계로 쪼갤 수 있다”는 순수하게 조합론적인 성질과 같은 방향을 가리킨다는 선언이다. 두 세계를 잇는 다리 자체가 결과인 셈이다.

3. 반전: 유계가 아니라 “거의” 유계다

여기서 가장 먼저 걸리는 단어가 “거의”다. 유계(bounded)가 아니라 거의 유계(almost bounded)다. 이 차이는 수사가 아니라 정리의 내용이다. 병합 폭에 상한 상수가 존재한다고 주장하는 것이 아니라, 어떤 의미에서 상한에 가까워진다고 주장한다. 논문의 제목이 “Have Almost Bounded Merge-Width”인 이유가 여기에 있다.

이 완화는 흠이 아니라 필연으로 보인다. 모나딕 의존성은 클리크 폭 유계보다 넓은 우산이고, 넓은 우산 아래에는 폭이 아무리 커도 되는 클래스가 들어 있다. 그런 클래스까지 상수 상한으로 묶으려 하면 정리가 거짓이 된다. 따라서 “거의”는 증명의 게으름이 아니라 대상의 성질을 정확히 반영한 표현이다.

독자가 붙잡아야 할 반전은 이것이다. 이 논문은 “규칙적인 그래프는 작은 폭을 가진다”는 오래된 직관을 그대로 확인하지 않는다. 대신 “규칙적이라는 말의 정확한 의미를 모델 이론의 언어로 잡으면, 폭은 상수가 아니라 점근적 한계로만 묶인다”고 말한다. 상수를 기대한 사람에게는 약화이고, 넓은 클래스를 상대하는 사람에게는 충분한 보상이다.

4. 경쟁 가설: 왜 다른 폭 척도가 아니었나

같은 질문에 답할 후보는 여럿이었다. 트리 폭은 너무 좁다. 나무처럼 생기지 않은 빽빽한 그래프를 배제하기 때문에, 모나딕 의존적인 클래스를 담지 못한다. 클리크 폭은 후보로 자연스럽지만, 클리크 폭 자체를 계산하는 일이 일반적으로 매우 어렵고, 클리크 폭 유계보다 넓은 모나딕 의존 클래스를 상수로 묶지 못한다.

그래서 저자들이 택한 것이 병합 폭이다. 병합 열이라는 형태는 증명이 만들어 내는 대상과 알고리즘이 소비하는 대상이 같은 모양이 되게 한다. 이것이 “증명은 되었는데 분해를 계산할 수 없다”는 흔한 난점을 피하는 설계다. 폭 개념을 고르는 일 자체가 결과의 절반이라는 점을 이 대목이 보여 준다.

나무 분해(tree decomposition)의 예. 트리 폭은 “작은 경계로 쪼갠다”는 아이디어의 원형이지만, 빽빽한 그래프를 담기에는 너무 좁다 — David Eppstein, Public domain (Wikimedia Commons)

반론도 가능하다. “거의 유계”가 실제 알고리즘에서 쓸모 있는가. 상한이 점근적이라면, 입력 크기가 유한한 현실에서는 그 상한이 얼마든지 커질 수 있지 않은가. 이 반론은 정당하다. 다만 논문은 그 반론을 피하지 않고, 알고리즘의 실행 시간을 별도로 제시하는 쪽으로 답한다.

5. 방법: 증명이 곧 알고리즘이다

초록은 이 증명이 알고리즘적이라고 밝힌다. 증인에 해당하는 분해, 즉 병합 열을 실제로 계산할 수 있고, 그 시간은 거의 세제곱 시간(nearly-cubic time)이다. 존재성 증명에 그치지 않고 구성 절차를 준다는 뜻이다. 그래프 알고리즘에서 이 차이는 결정적이다. 존재만 알면 그 그래프를 다룰 수 없지만, 다항 시간에 분해를 뽑을 수 있으면 그 위에 다른 알고리즘을 얹을 수 있다.

세제곱은 빠르지 않다. 정점 1,000개면 10억에 가까운 연산 규모다. 그러나 이 분야에서 세제곱은 “원리적으로 가능하다”를 넘어 “구현해서 실험할 수 있다”는 경계선에 가깝다. 그리고 이 논문의 목표는 실용 최적화가 아니라 이론의 빈칸을 닫는 것이다.

6. 이 논문이 스스로 인정한 한계

초록이 명시하는 가장 큰 한계는 목표가 아직 도달하지 않았다는 점이다. 논문은 스스로를 “모나딕 의존적 클래스 위에서 1차 논리 모델 검사의 고정 매개변수 처리 가능성(fixed-parameter tractability)을 향한 한 걸음”이라고 부른다. 즉 이 논문만으로 모델 검사 알고리즘이 완성되지 않는다. 그 완성은 같은 저자들의 동반 논문(companion paper)에서 이루어진다고 초록은 적는다.

두 번째 한계는 앞서 말한 “거의”다. 상수 상한이 아니므로, 어떤 클래스에서는 병합 폭이 여전히 입력과 함께 커진다. 세 번째는 시간 복잡도다. 거의 세제곱은 다항이지만, 매개변수화 알고리즘의 관점에서는 여전히 무거운 출발점이다. 이 세 가지를 논문이 부정하지 않는다는 점에서, 이 글은 초록이 밝힌 범위까지만 주장한다.

7. 독자에게: 규칙성의 값은 얼마인가

이 결과가 던지는 질문은 기술적이지 않다. “규칙적이다”라고 말할 때 우리는 무엇을 포기하고 무엇을 얻는가. 모나딕 의존성은 매우 관대한 규칙성이다. 그 관대함의 대가로 폭은 상수가 아니라 점근적 한계로만 주어진다. 반대로 상수를 얻으려면 규칙성을 더 좁혀야 하고, 그러면 담을 수 있는 그래프가 줄어든다. 이 논문은 그 교환비를 정확히 재는 작업에 속한다.

한 가지 확인해 두자. 필자는 이 논문의 병합 폭 정의와 증명 기법을 원문 수준에서 검토하지 않았다. 이 글의 서술은 arXiv 초록과 제목, 저자, 공개 날짜에 근거하며, 병합 폭의 세부 정의와 증명 구조는 원문을 직접 읽어야 한다. 특히 “거의 유계”의 정확한 의미는 초록만으로 확정할 수 없다.

여러분에게 묻고 싶다. 여러분이 다루는 데이터나 코드 구조는 “규칙적”한가, 아니면 그 안에 임의의 그래프를 흉내 낼 수 있을 만큼 자유로운가. 만약 후자라면, 그 자유로움이 실제로 값을 하고 있는지 아니면 그저 우연히 쌓인 복잡성인지 — 어느 쪽이라고 생각하는가.

참고 자료

Dreier, J., Mählmann, N., Pilipczuk, M., Toruńczyk, S., “Monadically Dependent Graph Classes Have Almost Bounded Merge-Width”, arXiv:2611.06804v1 [math.LO], 2026-11-04. https://arxiv.org/abs/2611.06804v1

이미지 출처: Wikimedia Commons — Clique-width construction (David Eppstein, Public domain), Tree decomposition (David Eppstein, Public domain).