100만 정점에서 일곱 쌍을 묻는다 — 1차 논리 판정이 빨라지는 그래프의 경계가 확정됐다 (arXiv 2611.08143v1)

정점이 100만 개인 그래프가 손에 있다고 하자. 간선은 수백만 개, 어디에도 격자가 보이지 않고, 어딘가에 하나짜리 사이클도 없다. 여기서 던지는 질문은 이렇다. 이 그래프의 정점 일곱 쌍이 서로 간선으로 이어져 있는지, 즉 하나의 1차 논리(first-order logic) 문장이 참인지 거짓인지만 알고 싶다. 문장의 길이는 고정되어 있고, 그래프는 입력이다. 순진하게 모든 일곱 쌍을 세어 보면 10^42에 가까운 조합이 나온다. 그런데 2026년 11월 5일 arXiv에 올라온 논문 하나는, 특정한 종류의 그래프 집합에서는 이 판정이 입력 크기의 다항식 시간에, 그것도 문장 길이에만 의존하는 지수 인자로 끝난다고 주장한다. 저자는 Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk 세 사람이고, 제목은 「First-Order Model Checking on Monadically Dependent Graph Classes」다.

이 글에서 다룰 것은 그 '특정한 종류'가 무엇이며, 왜 그 경계가 지난 20년 동안 알고리즘 모델 이론의 중심 질문이었는가다. 결론을 먼저 말하면, 논문은 '1차 논리 판정이 빠른 그래프 집합'을 정확히 하나의 성질로 특징짓는 분류를 완성했다고 주장한다. 조건도 결론도 완전한 if-and-only-if이며, 그 사이의 증명은 구조 그래프 이론과 유한 모델 이론, 그리고 모델 이론의 타입 세기를 한 상자에 넣는다.

1. '고정 매개변수'라는 말이 실제로 하는 일

먼저 문제를 정확히 세워야 한다. 입력은 그래프 G 하나이고, 함께 고정된 1차 논리 문장 φ가 있다. φ 안의 변수 개수와 중첩 깊이는 상수로 못 박혀 있고, 판정해야 할 것은 G가 φ를 만족하는가다. 여기서 '고정 매개변수 다루기 쉬움(fixed-parameter tractable, FPT)'이란 실행 시간이 f(φ) · |G|^c 꼴이라는 뜻이다. φ가 길어지면 지수적으로 느려져도 좋지만, G가 커지는 데 대해서는 다항식이어야 한다. 다시 말해 문장은 비싸도 그래프는 싸게 처리해야 한다.

이 정의가 왜 까다로운지 보려면 반대편을 보면 된다. 그래프 집합이 나쁘게 생겼다면, 문장 하나로 그래프의 크기에 비례하는 계산을 강제할 수 있다. 예컨대 어떤 집합에서는 문장 하나가 '이 그래프에 크기 n의 독립집합이 있다' 같은 전역적 조건을 흉내 내고, 그러면 판정은 자연히 NP-난해 쪽으로 끌려간다. 즉 FPT 여부는 알고리즘의 영리함 문제가 아니라, 그래프 집합이 1차 논리로 어디까지 자기를 부호화할 수 있느냐의 문제다. 논문이 던지는 질문은 그래서 알고리즘 질문이면서 동시에 논리 질문이다.

2. 모나딕 의존성 — '자기를 복제하지 못하는' 집합

논문이 쓰는 조건은 모나딕 의존성(monadic dependence)이다. 정의를 풀면 이렇다. 그래프 집합 C가 모나딕 의존적이라는 것은, C의 원소들에 정점 색칠을 아무리 자유롭게 얹어도, 고정된 하나의 1차 논리 공식만으로는 모든 그래프를 그 안에 해석(interpret)해 낼 수 없다는 뜻이다. '해석'은 비유가 아니라 모델 이론의 정식 절차다. 공식 몇 개로 원본 구조의 원소를 골라내고, 그 위에 관계를 다시 정의해 전혀 다른 구조를 복제해 넣는 작업이다.

따라서 이 조건은 표현력의 상한을 말한다. 색칠을 바꿔 가며 모든 그래프를 흉내 낼 수 있는 집합은 너무 강력해서, 그 위에서는 1차 논리 판정이 빠를 수 없다. 반대로 흉내가 막히는 집합은 어딘가 구조적으로 규칙적이다. 논문이 강조하는 것은 이 조건의 포괄성이다. 국소적으로 희박한(nowhere dense) 집합 전부와, 트윈 폭(twin-width)이 유계인 집합 전부가 여기에 들어간다. 서로 다른 두 연구 전통이 각자 쌓아 온 결과가 하나의 이름 아래 묶인다는 뜻이고, 그래서 이 조건에서 FPT를 보이면 그 두 결과를 동시에 덮는다.

금지된 유도 부분그래프의 예 — 발톱(claw), 태양(sun), 그물(net)과 길이 4 이상의 사이클. 이런 국소적 금지 패턴이 집합의 규칙성을 규정한다. — David Eppstein, CC0 (위키미디어 공용)

3. 정리: 조건이 곧 답이 된다

논문의 주 결과는 두 방향을 합쳐 하나의 등식으로 읽힌다. 한 방향은 새로 증명한 것이다. 모든 모나딕 의존 그래프 집합에서 1차 논리 모델 체킹은 FPT다. 다른 방향은 이미 알려져 있었다. 모나딕 의존적이지 않은 상속(hereditary) 집합에서는 FPT가 성립하지 않는다는 난해성 결과다. 둘을 붙이면, 상속 집합에 대해 'FPT다'와 '모나딕 의존적이다'가 같은 말이 된다. 논문은 이것을 상속 그래프 집합에서의 완전한 특징짓기라고 부르고, 알고리즘 모델 이론의 중심 미해결 문제를 해결했다고 주장한다.

여기서 '상속'이라는 단서가 중요하다. 상속 집합은 유도 부분그래프를 취해도 닫혀 있는 집합이다. 정점 하나를 지워도 그 집합에 남는다는 뜻이고, 이 성질이 없으면 분류 자체가 성립하지 않는다. 독자가 흔히 기대하는 '모든 그래프 집합'에 대한 분류가 아니라는 점은 뒤에서 한계로 다시 다룬다. 분류의 대상은 어디까지나 유도 부분그래프에 닫힌 집합으로 한정된다.

4. 반전은 증명의 재료에서 나온다

직관은 이렇다. 그래프가 규칙적이면 작은 조각으로 잘게 쪼갤 수 있고, 조각 경계를 넘나드는 정보만 세면 문장을 판정할 수 있다. 실제로 국소성(locality) 정리와 분해 정리가 그런 방향의 도구다. 그런데 이 조합만으로는 다 되지 않는다. 조각의 경계가 복잡해지면, 경계 위에서 가능한 '타입'의 수가 통제를 벗어나기 때문이다. 여기서 논문이 꺼내는 것이 모델 이론의 타입 세기다.

논문이 증명하는 핵심 보조정리는 숫자 하나로 요약된다. 모나딕 의존 집합에서는, 고정된 길이의 튜플이 고정된 양화사 계수(quantifier rank)에 대해 가질 수 있는 타입의 수가, 임의의 매개변수 집합 U 위에서 |U|의 다항식 개수, 즉 |U|^{O(1)}개를 넘지 않는다. 지수가 아니라 다항식이다. 이 보조정리가 있으면 경계 위의 가능한 상태를 다항 개로 접어 둘 수 있고, 접힌 상태 위에서 동적 계획을 돌리면 FPT가 나온다. 구조 이론이 뼈대를 세우고, 타입 세기가 살을 붙이는 구조다.

클릭 폭(clique-width) 구성 연산으로 만든 거리 유전 그래프. 정점 집합을 묶고 다시 잇는 연산이 분해의 뼈대가 된다. — David Eppstein, CC0 (위키미디어 공용)

5. 경쟁 가설과 반론

가장 자연스러운 경쟁 가설은 '분해 폭' 하나로 충분하다는 쪽이었다. 실제로 트윈 폭 유계 집합과 국소적 희박 집합은 각각 독립적으로 FPT를 보였고, 두 집합의 합집합이 답이 아닐까 하는 기대가 있었다. 반론은 명확하다. 모나딕 의존성은 그 둘보다 넓고, 넓어진 만큼 분해 도구가 그대로 먹히지 않는다. 두 도구가 각각 닿지 못하는 영역이 있고, 그 사이를 잇는 별도의 논증이 필요하다. 논문은 그 별도의 논증을 타입 세기에서 찾았다는 것이고, 이것이 기존 결과를 '특수한 경우'로 흡수한다.

또 하나의 반론은 실용성이다. f(φ)가 문장 길이에 지수적이면, 실제로 쓸 만한 문장 크기에서 상수가 감당이 안 될 수 있다. 이 반론은 정리의 참됨을 흔들지 않지만 의미를 좁힌다. 이 결과는 '지금 당장 돌려 볼 알고리즘'이 아니라 '어디까지가 원리적으로 가능한가'의 지도에 가깝다. 저자들도 증명이 세 분야를 결합한다는 점을 강조하며, 이 결과의 값어치를 경계의 확정에 둔다.

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

첫째, 분류는 상속 집합에 한정된다. 상속이 아닌 집합, 예컨대 정점을 지우면 집합을 벗어나는 경우에는 이 등식이 그대로 성립한다고 말할 수 없다. 둘째, 결과는 존재성과 복잡도 상한에 관한 것이고, f(φ)의 구체적인 형태나 실제 구현 가능한 상수는 제시되지 않는다. 셋째, 증명이 세 분야의 정리를 겹겹이 쌓아 올린 형태라, 각 단계의 가정이 어디까지 필요한지에 대한 최적성은 남는 질문이다.

이 한계들은 결과를 약하게 만들지 않는다. 오히려 어디까지가 이 정리의 사정권인지를 분명히 해 준다. 독자가 이 논문을 인용할 때 조심해야 할 지점도 여기다. '모든 그래프에서 1차 논리 판정이 빠르다'가 아니라, '상속 집합 중 모나딕 의존적인 것 전부에서 빠르고, 그 밖에서는 빠를 수 없다'가 정확한 문장이다.

7. 그래서 무엇이 남는가

이 정리의 진짜 무게는 숫자가 아니라 지도에 있다. 지난 20년 동안 연구자들은 여러 조건을 하나씩 제안하고, 각 조건마다 FPT 증명을 따로 쌓았다. 이 논문은 그 조건들을 하나로 접고, 접은 선이 최적임을 보인다. 조건을 더 넓히면 즉시 반례가 나오고, 더 좁히면 이미 알려진 경우가 빠진다. 분류 문제에서 이보다 깔끔한 결말은 드물다.

여러분에게 던지는 질문은 이것이다. 여러분이 다루는 데이터 구조나 네트워크가 어떤 집합에 속하는지 판정할 수 있다면, 그 집합이 모나딕 의존적인지 먼저 확인해 보겠는가. 아니면 여전히 '우리 문제는 특수해서 이론이 닿지 않는다'고 믿겠는가. 이 논문은 그 두 번째 믿음이 생각보다 자주 틀린다는 것을, 조건 하나로 정리해 버렸다.

참고 자료

Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk, “First-Order Model Checking on Monadically Dependent Graph Classes”, arXiv:2611.08143v1 (2026-11-05). https://arxiv.org/abs/2611.08143v1