TAMREF's profile image

TAMREF

September 9, 2022 00:00

Introduction

문제 해결을 하다 보면 종종 몇 가지 조건들을 더하고 빼며 문제를 확장시키거나, 더 포괄적인 문제를 해결합니다. 지난 글 에서는 추상화를 통해 문제를 확장하는 일련의 과정을 느낄 수 있었습니다. 이번에는 반대로 원하는 답에 몇 가지 추가적인 조건을 덧붙여 구체화된 문제를 어떻게 해결하는지 들여다보도록 합시다.

“단순 무방향 그래프 $G$에 사이클이 존재하느냐?” 라는 기초적인 질문에서 출발합니다. DFS를 이용하여 해결할 수 있는 문제죠. 이 문제만 해도 몇 가지 방향으로 확장할 수 있습니다.

• 최소 길이: “$G$에 길이가 $k$ 이하인 사이클이 존재하는가?”
• 방향성 부여: “$G$가 방향그래프일 때, 사이클이 존재하는가?”
• 기우성: “$G$에 길이가 홀수인 사이클이 존재하는가?”
  • 이는 $G$가 이분그래프(bipartite graph)인 것과 동치입니다.

이런 변종들도 DFS, BFS의 범위를 크게 벗어나지 않고 해결할 수 있습니다. 괜히 한 번 조건들을 섞어봅시다.

• $G$가 방향그래프일 때, 가장 짧은 사이클을 찾을 수 있는가?
• $G$가 방향그래프일 때, 홀수 사이클을 찾을 수 있는가?
  • 더 이상 $G$가 이분그래프인지 여부와 직접적인 연관성은 없습니다.
• $G$가 방향그래프일 때, 가장 짧은 홀수 사이클을 찾을 수 있는가?

이 문제들 또한 약간의 기술을 곁들여 해결할 수 있습니다. 홀수만 나오면 섭섭하니, 짝수도 좀 넣어볼까요?

• 무방향그래프에서 짝수 사이클을 찾을 수 있는가?
• 무방향그래프에서 가장 짧은 짝수 사이클의 길이를 찾을 수 있는가?
• 방향그래프에서 짝수 사이클을 찾을 수 있는가?
• 방향그래프에서 가장 짧은 짝수 사이클을 찾을 수 있는가?

홀수 사이클이 찾기 쉬우니 짝수라고 크게 어려울까 싶겠습니다마는, 놀랍게도 저 4문제 모두 간단치가 않습니다. 또한, 4문제를 해결하는 최신 방법의 연구 분야는 겹치는 것이 없는 수준입니다.

이 글에서는 위의 4문제 중 가장 늦게까지 버텨낸 방향그래프에서 가장 짧은 짝수 사이클 (Shortest Even Length Cycle) 을 찾는 문제를 해결한 A. Bjorklund et al (이하 Bjorklund)의 방법을 리뷰하고, 이를 코드로 구현한 이야기를 다룹니다.

Solutions to Other Variants

Bjorklund의 방법이 왜 신기한지 느끼기 위해서, 다른 연습문제에 대한 풀이를 보도록 합시다.

Clarifications

이 글에서 cycle이란 “simple cycle”로, 정점도 간선도 중복해서 사용하지 않는 닫힌 경로를 의미합니다. 또한 공집합을 길이 $0$인 사이클로 생각하지 않습니다. 마지막으로, 길이에는 가중치가 없습니다. 모든 간선은 길이 $1$짜리 간선으로 생각합니다.

1. Finding the shortest cycle in a (di)graph (girth)

모든 정점 $v$에 대해서, 간선 $u \to v$가 있다면 $\mathrm{dist}(v \to u) + \mathrm{weight}(u \to v)$의 최솟값이 답이 됩니다. 이는 모든 점에서 BFS를 하면 $O(n(n+m))$ 시간에 해결할 수 있습니다. 이는 최악의 경우 $O(n^3)$ 시간이 되는데, Shortest cycle problem의 sub-cubic algorithm이 존재하는 것은 APSP(All-Pair Shortest Path)의 sub-cubic algorithm이 존재하는 것과 동치이기 때문에 이 하한을 개선하기는 쉽지 않습니다.

2. Finding an odd cycle from a digraph

Digraph를 DFS 순서로 두면, 사이클의 존재성은 back edge (자식에서 조상으로 가는 간선) 의 존재와 동치가 됩니다. 홀수 사이클은 어떻게 찾을 수 있을까요?

그래프의 정점 $v$를 $v _ {0}, v _ {1}$으로 쪼갠 뒤, 간선 $u \to v$를 $u _ {0} \to v _ {1}$, $u _ {1} \to v _ {0}$으로 바꾸어줍니다. 원래 그래프에서 $v$를 포함하는 홀수 사이클이 존재하는 것은, $v _ {0}$에서 $v _ {1}$으로 가는 경로가 존재하는 것과 동치가 됩니다. 이를 DFS를 이용하여 찾아주면 $O(n + m)$ 시간에 홀수 사이클을 찾아줄 수 있습니다. 해당 문제는 2015년 대전 리저널에 어려운 문제로 출제되었습니다.

이를 이용하여 모든 정점 $v$에 대해 $v _ {0} \to v _ {1}$으로 가는 최단경로를 찾아주면 가장 짧은 홀수 사이클을 찾을 수 있습니다. 사실 여기서 생략한 사실은, 가장 짧은 홀수 길이 closed-walk이 곧 가장 짧은 홀수 사이클이 된다는 것입니다. closed-walk이 한 정점을 두 번 방문하게 된다면, 그 점을 기준으로 더 작은 홀수 길이 closed-walk을 만들 수 있기 때문입니다.

짝수 cycle에 대해서는 비슷한 논리가 성립하지 않습니다. $3 \to 1 \to 2 \to 3 \to 4 \to 5 \to 3$이라는 길이 $6$짜리 closed walk은 짝수 길이 사이클을 포함하지 않기 때문입니다.

3. Even cycle in an undirected graph

Even cycle은 odd cycle에 비해 직관적으로 찾기도 어렵고, 찾았다고 해서 beneficial한 부분이 명확하지도 않아서 널리 알려져 있진 않습니다. 다음의 예제에서 출발해봅시다.

Proposition. 단순 무방향그래프 $G$의 minimum degree가 $3$ 이상이라고 하자. 이 때 선형 시간에 even cycle을 찾을 수 있다.

Proof. $G$의 maximal한 path $P$를 잡읍시다. 즉, $P$의 끝점 $v$에서 정점을 더 추가할 수 없으면 됩니다. $\deg (v) \ge 3$이므로, $v$에서 뻗어나가는 두 간선은 $P$의 정점과 이어져 있어야 합니다. 이를 각각 $a, b$라고 두면 $P + ab$, $P + bv$, $P + av$는 서로 다른 3개의 cycle을 만듭니다. 세 사이클의 길이가 모두 홀수일 수 없으므로, 셋 중 하나는 짝수 사이클이 됩니다. $\square$

홀수 사이클로만 이루어진 그래프를 생각하면, minimum degree가 $2$더라도 짝수 사이클을 포함하지 않을 수도 있습니다. 그런데 생각해보면 홀수 사이클에 간선을 하나만 추가해도 짝수 사이클이 하나 생기게 됩니다. 놀랍게도, 다음 정리는 홀수 사이클이 사실상 maximal한 반례임을 입증합니다.

Theorem. (Arkin) Simple $2$-connected graph $G$가 홀수 사이클이 아니라고 하자. $G$에는 짝수 사이클이 존재한다.

Note. 여기서 $2$-connected graph란 정점이 $3$개 이상이고, 단절점이 존재하지 않는 그래프를 의미합니다.

Proof. $G$의 사이클 $C$를 찾았다고 합시다. $C$가 짝수이면 끝이니 $C$가 홀수 사이클이라고 가정합니다. 이제 $G$에서 $C$의 간선들을 모두 제거한 그래프 $G’$을 생각합시다. $G \neq C$이므로, $G’$에서 $C$의 서로 다른 두 정점을 잇는 최단 경로 $P$가 존재합니다. $C$에 chord가 있었다면 그 chord를 $P$로 둘 수 있고, 그렇지 않다면 $v \in V(G) - V(C)$가 존재해야 하는데 $2$-connected 성질에 의해 $v$는 최소한 $C$의 서로 다른 두 정점과 경로로 연결되어 있어야 하기 때문입니다.

이러한 $v$들 중 가장 가까운 $C$의 두 점까지의 거리 합이 제일 짧은 정점 $v$를 고르면 자연히 경로 $P$를 찾게 됩니다. $P$의 두 정점이 $C$를 두 경로 $Q _ {1}, Q _ {2}$로 쪼개게 되는데, $P \cup Q _ {1}$과 $P \cup Q _ {2}$ 중 하나가 짝수 사이클이 됩니다. $\square$

증명 과정을 그대로 선형 시간의 알고리즘으로 옮길 수 있습니다. 경로 $P$를 찾는 과정은 multi-source BFS 등으로 가능합니다.

Corollary. 단순 무방향그래프 $G$에 even cycle이 존재할 필요충분조건은 $2$-connected component (edge-disjoint BCC) 중 “홀수 사이클이 아닌 정점 $2$개 이상을 가진 컴포넌트” 가 존재하는 것이다. 따라서, even cycle의 존재 유무를 판별하고 존재한다면 하나를 찾는 $O(n + m)$ 시간 알고리즘이 존재한다.

4. Shortest Even Cycle in undirected graphs

홀수 사이클과는 다르게, shortest even cycle은 그냥 even cycle을 찾는 것 보다는 훨씬 어렵습니다. 가장 인상적인 풀이는 General Matching을 이용한 풀이입니다.

이번에도 그래프의 정점과 간선을 복제합니다. $v$를 $v _ {0}$와 $v _ {1}$으로 분해하고, 간선 $uv$를 $u _ {0}v _ {0}$, $u _ {1}v _ {1}$으로 분해합니다. 대신 이번에는 모든 정점에 간선 $v _ {0}v _ {1}$을 추가합니다. 편의상 기존 그래프의 간선을 ‘가로선’, 새로 추가한 $v _ {0}v _ {1}$ 형태의 간선을 ‘세로선’이라고 합시다.

모든 가로선의 가중치를 $0$, 세로선의 가중치를 $1$로 설정합시다. 이제 간선 $uv$를 지나는 shortest even cycle을 구할 것입니다. 간선 $u _ {0}v _ {0}$와 $u _ {1}v _ {1}$을 끊고, 새로운 정점 $s, t$를 추가하여 $u _ {0}s$, $v _ {0}t$를 이어줍시다. 이 때 이 그래프의 maximum weight perfect matching을 생각하면, $s, t$가 포함되어야 하니 $u _ {0}s$와 $v _ {0}t$는 무조건 매칭에 들어갑니다. 또한 $uv$를 포함하는 짝수 사이클이 존재하지 않는다면 perfect matching이 존재하지 않습니다.

그런 경우를 제외하면, maximum weighted perfect matching은 $uv$를 포함하는 가장 짧은 짝수 사이클을 구성하는 가로선들만 사용하고, 나머지는 가중치 $1$짜리 세로선을 사용하는 매칭이 됩니다. 이를 모든 간선에 대해 반복하면 General matching에 걸리는 시간의 $n^{2}$배 정도에 문제를 해결할 수 있습니다.

Yuster & Zwick은 Shortest Even Length Cycle이 가질 수 있는 structure에 집중하여 $O(n^2)$ 시간에 shortest even length cycle을 찾는 알고리즘을 Finding even cycles even faster 라는 논문에서 공개하였습니다. 지면 관계상 여기서는 생략하도록 하겠습니다.

5. Even cycle in digraphs

앞선 문제들이 대부분 80년대에 Polynomial algorithm이 나온 것과는 다르게, 방향그래프에서 짝수 길이 사이클을 찾는 문제는 오랫동안 다항 시간에 풀리지 않았습니다. 오히려 반대로, 이보다 더 복잡한 문제는 풀기 어렵다는 것이 밝혀지기도 했습니다.

Theorem (Arkin) 다음 문제들은 NP-complete이다.

• 방향그래프에서 정점 $v$를 지나는 odd length cycle이 존재하는가?
• $a > 2, b > 0$에 대해 길이가 $ax + b$ 꼴인 cycle이 존재하는가?
• $a > 1, b \ge 0$에 대해 정점 $v, w$에 대해 $v$에서 $w$로 가는 길이가 $ax + b$ 꼴인 (혹은 그런 꼴이 아닌) cycle이 존재하는가?

그런데 종종 그래프 이론 논문을 보다 보면, Robertson, Seymour, Thomassen, Thomas, Kawarabayashi 등의 이름을 자주 보게 되곤 합니다. 이들은 주로 graph theory 분야의 문제들을 graph classification으로 환원하여 해결하는 업적을 많이 남겼는데, Even cycle problem의 경우에도 90년대 후반에 이들에 의해 정복되었습니다. 이를 간단하게만 요약해봅시다.

80-90년대에 방향그래프의 even cycle을 찾는 문제와 동치인 몇 가지 문제들이 발견되었습니다.

Theorem (Vazirani) 다음 문제들은 서로 polynomial-time reducible하다.

• (Polya’s problem) 주어진 $0$-$1$ 행렬 $A$에 대해, $A$의 entry 몇 개에 $-1$을 곱한 matrix $B$를 만들어 $\mathrm{perm}(A) = \det B$가 되도록 할 수 있는가?
  • $\mathrm{perm}(A)$는 determinant의 정의에서 $\mathrm{sgn}(\sigma)$ 항이 빠진 값으로, permanent라고 부릅니다. $A$를 이분그래프의 adjacency matrix로 보면, 이 이분그래프의 perfect matching 개수와 동일합니다.
• (Even Cycle Problem) 방향그래프에 짝수 길이 사이클이 존재하는가?
• (Pfaffian orientation problem) 이분그래프가 주어졌을 때, 간선에 “Pfaffian orientation”을 줄 수 있는가?

Pfaffian orientation의 정의만 읊자면, 이분그래프의 간선에 방향성을 주는 방법입니다. 이분그래프의 사이클 $C$ (무조건 짝수 길이) 가 “central”하다는 것은, $V(G) - V(C)$에 perfect matching이 존재한다는 것입니다. 즉, perfect matching을 만들 때 $G - C$에서만 따로 만들고, $C$에서는 두 가지 방법 중 아무거나 골라서 perfect matching을 만들 수 있다는 것입니다.

Pfaffian orientation이란, 모든 central cycle에 대해 이를 구성하는 간선의 방향 (임의로 cycle을 따라갔을 때, 간선이 cycle을 따라 났는지 반대로 났는지) 에 따라 분류했을 때 홀수 개씩 쪼개지는 orientation을 말합니다. 말이 너무 복잡하지만, 결국은 무방향 이분그래프라는 다루기 쉬운 대상에 정의되는 성질입니다.

Robertson, Seymour, Thomassen 등은 Pfaffian orientation이 존재하는 bipartite graph의 structural classification (forbidden minor classification)에 성공했습니다. 그리고 그들에게는 어떤 성질 $P$의 structural classification만 있으면 아무 그래프 $G$가 성질 $P$를 갖는지 $O(n^3)$ 시간에 테스트할 수 있는 강력한 도구, Robertson-Seymour theorem이 있습니다.

따라서 방향그래프의 even cycle이 찾고 싶다면 이를 pfaffian ordering problem으로 환원한 다음 Robertson-seymour theorem의 알고리즘으로 해결하면 됩니다. 이러한 문제 풀이 scheme에 대해서는 기회가 되면 다루어보도록 하겠습니다.

Shortest even cycle in directed graph

“Shortest”, “Even”, “Directed”라는 세 가지 키워드 중 하나라도 빠진 문제는 앞에서 전부 해결했지만, 그 중 어느것도 이 문제를 해결할 수 있는 방향으로 일반화되지 못했습니다.

우선 even cycle problem에서 loop는 전혀 고려 대상이 아니니, 방향그래프 $G$의 모든 정점에 loop가 달려 있다고 가정합시다. 이제 간선 $uv \in E(G)$에 미지수 $w _ {uv}$를 할당하고, 이를 기반으로 한 인접행렬 $A$를 만듭니다.

\[A _ {uv} = \begin{cases} w _ {uv} & uv \in E(G) \\ 0 & \text{otherwise} \end{cases}\]

$G$의 cycle $C$에 대해, $w(C)$를 $\prod _ {e=uv \in E(C)} A _ {uv} = \prod _ {e \in E(C)} w _ {e}$로 정의합시다. 이렇게 되면 $\det A, \mathrm{per} A$를 Cycle cover의 항으로 쓸 수 있게 되는데, cycle cover란 간선이 $n$개인 vertex-disjoint cycle들의 모임을 말합니다. 구체적으로 Cycle cover $\mathcal{C} = (C _ {1}, \cdots, C _ {k})$에서 $\kappa(C) := k$로 정의하면,

\[\det A = \sum _ {\sigma} \mathrm{sgn}(\sigma) \prod _ {i = 1}^{n} A _ {i, \sigma _ {i}} = \sum _ {\mathcal{C} : \text{ cycle cover}} (-1)^{n - \kappa (\mathcal{C})} \prod _ {i=1}^{\kappa(\mathcal{C})} w(C _ {i})\] \[\mathrm{per} A = \sum _ {\sigma} \prod _ {i = 1}^{n} A _ {i, \sigma _ {i}} = \sum _ {\mathcal{C} : \text{ cycle cover}} \prod _ {i=1}^{\kappa(\mathcal{C})} w(C _ {i})\]

이 때 각 $\mathcal{C} = (C _ {1}, \cdots, C _ {k})$에 대해, $\lbrace w _ {ij} \rbrace$로 이루어진 square-free polynomial $W(\mathcal{C}) := \prod _ {i = 1}^{k} w(C _ {i})$는 $\mathcal{C}$마다 distinct할 수밖에 없습니다. 이로부터 알 수 있는 사실은,

Proposition. 그래프 $G$에 even cycle이 존재하는 것은 $\frac{1}{2}(\mathrm{per} A - \det A) \neq 0$과 동치이다.

Proof. $\frac{1}{2}(\mathrm{per} A - \det A)$는 $\kappa(\mathcal{C})$가 홀수인 모든 $\mathcal{C}$에 대해 $W(\mathcal{C})$를 더한 것과 같습니다. $G$에 even cycle $C _ {0}$가 존재한다면, $C _ {0}$와 loop들로 구성된 cycle cover가 존재하므로 $\frac{1}{2}(\mathrm{per} A - \det A) \neq 0$이 될 수밖에 없습니다. 반대도 마찬가지입니다. $\square$

이 아이디어는 나아가서 shortest even cycle을 찾는 데까지 발전시킬 수 있습니다. 대각선 entry에 추가 변수 $y$를 곱하여 행렬 $A^{y}$를 만듭시다.

\[A _ {uv}^{y} = \begin{cases} yw _ {uu} & u = v \\ w _ {uv} & u \neq v, uv \in E(G) \\ 0 & \text{otherwise} \end{cases}\]

이 때, 마찬가지로 $\frac{1}{2}(\mathrm{per} A^{y} - \det A^{y})$에서 $y^{k}$의 계수는 사이클의 개수가 짝수이고, loop가 $n - k$ 개인 cycle cover의 $W$값들을 합한 것입니다. 따라서 $y^{n-k}$의 계수가 nonzero인 것과, 길이가 $k$인 even cycle이 존재하는 것은 동치가 됩니다.

Proposition. $G$의 shortest even cycle의 길이는 $\frac{1}{2}(\mathrm{per}A^{y} - \mathrm{det} A^{y})$ 에서 $y^{n - k}$의 계수가 $0$이 아니게 되는 최소의 양의 짝수 $k$와 같다. 물론 그러한 $k$가 존재하지 않으면, $G$에는 even cycle이 존재하지 않는다. $\square$

하지만 $\frac{1}{2}(\mathrm{per}A^{y} - \det A^{y})$의 식을 계산하는 건 당연히 매우 어려운 문제입니다. 그래서 아래와 같은 전략을 사용합니다.

1. 적당한 field $F$에 대해, $w _ {uv}$에 랜덤한 원소 $\beta _ {uv}$를 대입하여 행렬 $\mathcal{A}^{y}$를 만든다.

\(\mathcal{A}^{y} = \begin{cases} y\beta _ {uu} & u = v \\ \beta _ {uv} & u \neq v, uv \in E(G) \\ 0 & \text{otherwise} \end{cases}\) 이제 $\mathcal{A}^{y}$는 각 원소가 $F[y]$의 원소들이므로, $\det \mathcal{A}^{y}$는 그래도 다항 시간 내에 구할 수 있습니다. 구체적으로, $A$의 크기 ($G$의 정점 개수)가 $n \times n$이라면 $F$의 서로 다른 원소 $\gamma _ {0}, \cdots, \gamma _ {n}$에 대해 $\det \mathcal{A}^{\gamma _ i}$를 계산한 후 Lagrange interpolation을 해주면 되기 때문입니다. 하지만 여전히 아래와 같은 물음이 남아 있습니다.

• $\mathrm{per} \mathcal{A}^{\gamma _ i}$는 어떻게 계산할 것이냐?
• $\frac{1}{2}(\mathrm{per} \mathcal{A}^{y} - \det \mathcal{A}^{y})$의 $y^{k}$ 계수가 $0$이라고 해서, $\frac{1}{2}(\mathrm{per} A^{y} - \det A^{y})$의 $y^{k}$ 계수도 $0$이라는 보장이 없지 않느냐?

첫 번째 질문에 답을 잘 하는 것이 사실상 이 논문의 전부입니다. 여기서는 두 번째 질문을 먼저 해소하고 넘어갑시다.

1. $\beta$의 값을 여러 번 바꾸었을 때도 $\frac{1}{2}(\mathrm{per} \mathcal{A}^{y} - \det \mathcal{A}^{y})$의 $y^{k}$ 계수가 $0$이라면, 매우 높은 확률로 $\frac{1}{2}(\mathrm{per} A^{y} - \det A^{y})$의 $y^{k}$ 계수도 $0$이다.

사실 일변수 다항식으로 생각한다면 그리 어렵지 않은 것이, $N$차 다항식 $f(x) = 0$의 근은 Field $\mathbb{F}$에서 많아야 $N$개이고, $\beta$를 랜덤하게 뽑았을 때 ($\mathbb{F}$가 finite이라면) 최소한 $1 - \frac{N}{\lvert \mathbb{F} \rvert}$의 확률로 $f(\beta) \neq 0$이 됩니다. 대신 $\frac{1}{2}(\mathrm{per} A^{y} - \det A^{y})$의 $y^{k}$ 계수는 degree $n$의 square-free 다변수 polynomial이니, 그에 걸맞는 논의가 필요합니다.

Lemma. (Squarefree DeMillo-Lipton-Schwarz-Zippel) Degree가 $d$ 이하인 nonzero square-free polynomial $f \in \mathbb{F}[x _ {1}, \cdots, x _ {n}]$에 대해, $\mathbb{F}$의 랜덤한 원소 $\beta _ {1}, \cdots, \beta _ {n}$을 독립적으로 뽑으면 최소한 $(1 - \frac{1}{\lvert \mathbb{F} \rvert})^{d}$의 확률로 $f(\beta _ {1}, \cdots, \beta _ {n}) \neq 0$이다.

Proof. $d = 0$이면 성립하므로, 수학적 귀납법으로 $d-1$차 polynomial에 대해 이 사실이 성립한다고 합시다. $f(x _ {1}, \cdots, x _ {n})$에 대해 일반성을 잃지 않고 $x _ {n}$ 항이 포함되어 있다고 하고, $f = g(x _ {1}, \cdots, x _ {n-1}) + x _ {n} \cdot h(x _ {1}, \cdots, x _ {n-1})$로 씁시다. $G = g(\beta _ {1}, \cdots, \beta _ {n-1})$, $H = h(\beta _ {1}, \cdots, \beta _ {n-1})$이라고 두면 $H \neq 0$일 확률이 $(1 - \frac{1}{\lvert \mathbb{F} \rvert})^{d-1}$ 이상이고, 이 때 $\beta _ {n} \neq -GH^{-1}$이면 $f(\beta _ {1}, \cdots, \beta _ {n}) \neq 0$이므로 최소한 $(1 - \frac{1}{\lvert \mathbb{F} \rvert})^{d}$의 확률로 $f(\beta _ {1}, \cdots, \beta _ {n}) \neq 0$입니다. $\square$

추후 이야기드리겠지만 우리가 잡게 될 field $\mathbb{F}$는 크기가 $\Theta(n^{5})$ 정도이고, $d = n$ 정도가 됩니다. 따라서 $\beta$ 를 한 번 뽑는 시행에서 nonzero였던 계수가 억울하게 $0$으로 계산될 될 확률이 $O(n^{-4})$가 되므로, 사실 $\beta$ 값을 한 번만 추출해도 성공 확률이 매우 높은 과정이 됩니다.

이제 가장 어려운 질문인 $\mathrm{per} \mathcal{A}^{\gamma _ i}$는 어떻게 계산할 것이냐? 를 답할 준비를 해봅시다.

일찍이 Valiant (1979)에 의해 zero-one matrix의 permanent를 계산하는 것조차 $\sharp P$-hard라는 것이 알려졌습니다. 이를 생각해보면, 아무 field에 대해서 permanent를 계산하는 다항 시간 알고리즘이 아직 존재하지 않을 것이라고 예상할 수 있습니다. 대신 Valiant는 $\mathrm{per} A \mod{2^k}$를 $O(n^{4k - 3})$ 시간에 계산하는 알고리즘을 제시했습니다. 이와 관련된 문제로는 BOJ 7875 (False) Faces가 있습니다.

알고리즘의 원리를 잘 생각하면 $2^{k} x = 0$ $\forall x \in R$을 만족하는 모든 “적절한” ring $R$에 대해서, $R$의 원소로 구성된 matrix $A$의 permanent $\mathrm{per} A \in R$을 다항 시간에 구할 수 있습니다. 하지만 결국 앞선 Lemma나 Lagrange interpolation을 적용하기 위해서는 $\mathrm{per} A - \det A$가 적절한 Field 위로 떨어져야 합니다. 이런 점을 감안하고 보면 앞으로 이어질 construction을 납득하기 쉬워지는 면이 있습니다.

Galois field $\mathbb{F} _ {2^d} = \mathrm{GF}(2^{d})$는 일반적으로 degree $d$의 irreducible polynomial $g _ {2} \in \mathbb{Z} _ {2}[x]$에 대해 $\mathbb{Z} _ {2}[x] / \left< g _ {2}(x) \right>$ 으로 construct합니다. 이 때 $g _ {2}(x)$의 각 계수를 $\mathbb{Z} _ {4}$로 embedding한 다항식 $g _ {4}(x)$도 $\mathbb{Z} _ {4}[x]$의 irreducible polynomial이 되는데, Commutative ring $\mathbb{E} _ {4^d} = \mathbb{Z} _ {4}[x] / \left< g _ {4} (x) \right>$를 construct할 수 있습니다.

각각을 편의상 $\mathbb{F}$, $\mathbb{E}$라고 표기하겠습니다. $f \in \mathbb{Z} _ {2}[x]$에 대해 $f$의 계수를 $\mathbb{Z} _ {2}$에서 $\mathbb{Z} _ {4}$의 $\lbrace \overline{0}, \overline{1} \rbrace$ 로 보내는 “lifting” map $\lambda$, $h \in \mathbb{Z} _ {4}[x]$에 대해 $h$의 계수를 modulo 2를 취하는 “projection” map $\pi$를 정의하면, 각각의 quotient인 $\mathbb{F}, \mathbb{E}$에 대해서도 lifting / projection map이 정의되고, 특히 projection map은 ring homomorphism이 됩니다. 그 말인 즉슨, $\mathbb{E}$의 다항식을 project해서 $\mathbb{F}$의 다항식으로 만들 수 있습니다.

굳이 $\mathbb{E}$라는 ring을 디자인한 이유는 $\mathbb{F}$의 연산을 $\mathbb{E}$에서 “구현”할 수 있기 때문입니다. 우리는 $\mathrm{per} A$와 $\mathrm{det} A$를 $\mathbb{E}$에서의 다항식으로 보고 계산하지만, $2\lambda(f) = \mathrm{per} A - \det A$가 되는 $\mathbb{F}$ 위의 다항식 $f$를 찾아야 하기 때문입니다.

Proposition. $f \in \mathbb{E}[x _ {1}, \cdots, x _ {n}]$에 대해, $g = \pi(f) \in \mathbb{F}[x _ {1}, \cdots, x _ {n}]$이라고 두자. 임의의 $\tau _ {1}, \cdots, \tau _ {n} \in \mathbb{E}$에 대해 $2\lambda(g(\pi(\tau _ {1}), \cdots, \pi(\tau _ {n}))) = 2f(\tau _ {1}, \cdots, \tau _ {n})$ 가 성립한다.

Proof. $g = \pi(f)$이고, $\pi$가 ring homomorphism이므로 $\pi(f)(\pi(\tau _ 1), \cdots, \pi(\tau _ n)) = \pi\left( f(\tau _ 1, \cdots, \tau _ n) \right)$이 됩니다. 물론 $\lambda (\pi(x)) \neq x$이지만, 항상 $2\lambda(\pi(x)) = 2x$가 됩니다. $\square$

정리하면 행렬 $A$의 원소를 나타내는 미지수 $a _ {ij}$에 대해 $\mathrm{per} A$, $\det A$ 는 $a _ {ij}$에 대한 다항식 $\mathbb{E}[a _ {11}, \cdots, a _ {nn}]$으로 볼 수 있습니다. $\mathrm{per} A - \det A$ 또한 역시 다항식인데, 그 정의상 $2f = \mathrm{per} A - \det A$를 만족하는 $f \in \mathbb{E}[a _ {11}, \cdots, a _ {nn}]$ 또한 찾을 수 있습니다. 앞선 Lemma에 의해서, 아무 행렬 $B \in \mathbb{E}^{n \times n}$에 대해서 $\mathrm{per} B$와 $\det B$를 따로 계산하고 $\mathrm{per} B - \det B$를 “$2$로 나누고” $\pi$에 집어넣으면 됩니다.

$2$의 역원이 없어서 “2로 나눈다”는 말이 엄밀하지는 않으나, $\mathbb{E}$의 원소를 $g _ {4}(\alpha) = 0$을 만족하는 $\alpha \in \mathbb{E}$에 대한 다항식으로 나타내면 그 모든 계수가 $2$의 배수가 되기 때문에 $2\lambda(f) = \mathrm{per} B - \det B$를 만족하는 $f \in \mathbb{F}$를 쉽게 찾을 수 있습니다. 그러니까 이제 진짜 $B \in \mathbb{E}^{n \times n}$의 permanent만 구할 줄 알면 됩니다!

Permanent of $\mathbb{E}$-matrices

$\mathbb{Z} _ {2}$에서는 permanent와 determinant가 똑같기 때문에 그냥 가우스 소거법을 사용하면 permanent를 구할 수 있습니다. 또 $\mathbb{E}$는 $\mathbb{Z} _ {4}[x]$의 quotient이니, 아무 $e \in \mathbb{E}$에 대해 $4e = 0$이 됩니다.

Permanent는 Determinant처럼 multi-linear form이기 때문에, row vector나 column vector를 분리할 수 있습니다. 즉, column vector $v _ {1}, \cdots, v _ {n}$으로 이루어진 행렬 $A = \left( v _ {1}, \cdots, v _ {n} \right)$에 대해

\[\begin{aligned} \mathrm{per} (v _ {1}, \cdots, v _ {n}) &= \mathrm{per}(v _ {1}, \cdots, v _ {k-1}, x, v _ {k+1}, \cdots, v _ {n})\\ &+ \mathrm{per}(v _ {1}, \cdots, v _ {k-1}, v _ {k} - x, v _ {k+1}, \cdots, v _ {n}) \end{aligned}\]

이 성립합니다. 또 $A$에 존재하는 서로 다른 두 개의 column이 짝수인 경우, 즉 두 column $v _ {1}, v _ {2}$에 대해 $v _ {1} = 2w _ {1}, v _ {2} = 2w _ {2}$를 만족하는 $w _ {1}, w _ {2}$가 존재하는 경우 $\mathrm{per}(v _ {1}, v _ {2}, \cdots, v _ {n}) = 0$이 됩니다.

가우스 소거법을 하듯이, row operation을 이용하여 짝수 row가 많은 행렬을 만드는 것이 목표입니다.

Lemma. (Odd-elimination) $x = 2y$인 $y \in \mathbb{E}$가 존재하는 것과 $\pi(x) = 0$인 것은 동치이고, 이 성질을 만족하는 $x$를 짝수라고, 그렇지 않다면 홀수라고 정의한다. $x \in \mathbb{E}$가 홀수라면, 임의의 $y \in \mathbb{E}$에 대해 $y - kx$가 짝수인 $k \in \mathbb{E}$가 존재한다.

Proof. $\pi(x) \neq 0 \in \mathbb{F}$이므로 $\pi(x)$의 inverse $z$가 존재합니다. 이 때 $k = y\lambda(z)$로 두면 $\pi(y - kx) = \pi(y) - \pi(y) \pi(\lambda(z))\pi(x) = 0$. $\square$

이제 행렬 $A$의 permanent를 구하는 알고리즘을 생각해 봅시다. $k = 1, \cdots, n$에 대해,

• $k \le i, j \le n$에 대해 $a _ {ij}$가 홀수인 $i, j$를 찾습니다.
  • 그런 $k$가 존재하지 않는다면 반복문을 종료합니다.
• $j$번째 열과 $k$번째 열을 바꾸고, row operation을 이용하여 $k + 1$번째 열의 다른 odd entry를 지웁니다.
  • 가령 $a _ {l, k}$가 홀수라면, odd-elimination을 하는 계수 $z$를 구한 뒤 $l$번째 row에서 $i$번째 row의 $z$배를 뺍니다.
  • $A$를 row-vector $(x _ {1}, \cdots, x _ {n})$으로 나타내되, 편의상 $[x _ {l}, x _ {j}]$만 써서 나타내면 $\mathrm{per}[x _ {l}, x _ {j}] = \mathrm{per}[x _ {l} - zx _ {j}, x _ {j}] + \mathrm{per}[zx _ {j}, x _ {j}]$가 됩니다.
  • 이 중 $\mathrm{per}[zx _ {j}, x _ {j}]$는 다른 방법으로 나중에 구합니다. 이것들을 fragment라고 부릅시다.
• fragment를 따로 빼고, 남은 matrix에서 $i$행과 $k$행을 바꿉니다. 이제 생각해보면 맨 앞의 $n \times k$ matrix에는 홀수 entry가 $a _ {11}, \cdots, a _ {kk}$ 뿐입니다.

알고리즘이 끝났을 때, $O(n^{2})$개의 fragment와 “거의 짝수인” 행렬 하나가 남습니다. 알고리즘이 종료된 시점의 $k$에 따라서

• $k \ge n-1$이면, 단순히 대각 entry의 곱이 permanent가 됩니다.
• $k \le n-2$이면 짝수 row가 $2$개 이상이므로 permanent가 $0$입니다.

Fragments

두 Row $v _ {1}, v _ {2}$가 서로 비례하는 경우, $\mathbb{E}$에서 permanent를 determinant로 쉽게 바꾸어 구할 수 있습니다. 하지만 그냥 determinant를 구하면 $0$이 되므로, 서로 소거하는 $v _ {1i}v _ {2j}$와 $v _ {1j}v _ {2i}$를 분리해서 더할 필요가 있습니다.

이 때 row 1에 $t^{0}, t^{1}, \cdots, t^{n-1}$을 곱하고, row 2에 $t^{n-1}, \cdots, t^{0}$을 곱해서 determinant를 구하면 한 항은 $v _ {1i}v _ {2j} t^{n-1 + i -j}$, 다른 한 항은 $v _ {2i}v _ {1j} t^{n-1 + j-i}$ 가 되어 하나는 $n - 2$ 이하가 되고 다른 하나가 $n$ 이상이 되어 겹치지 않습니다. 따라서 determinant를 $t$에 대한 다항식으로 볼 때, $0$차항부터 $n - 2$차항 계수를 모두 더한 값이 permanent의 절반이 됩니다.

결국 determinant로 문제를 환원하는 데는 성공했으나, field의 determinant 대신 우리가 잘 모르는 다항식의 determinant입니다. 목표가 다항 시간이면 $\widetilde{O}(n^4)$ 번의 field operation으로 충분하지만, 여기서는 다항식의 column 평균 차수가 작아서 사용할 수 있는 알고리즘이 있습니다.

Theorem. (Labahn 2016) Finite field $\mathbb{K}$와 그에 대한 다항식 $\mathbb{K}[t]$을 정의하자. 각 원소가 $\mathbb{K}[t]$인 non-singular 행렬 $A$에 대해 $s$를 $A$의 row-degree (row별로 가장 높은 차수)의 평균과 column-degree (column별로 가장 높은 차수)의 평균 중 최솟값이라고 정의하면, $\widetilde{O}(n^{\omega})$ 시간에 $\det A$를 구하는 알고리즘이 존재한다.

지면 관계상 이 알고리즘의 증명은 생략하겠지만, 우리가 만든 행렬의 row degree 평균이 $2$ 이하이기 때문에 determinant를 $\widetilde{O}(n^{\omega})$ 시간에 구할 수 있습니다.

다만 non-singular 여부를 guarantee해야 하므로 이를 사전에 걸러 내어야 합니다. 랜덤한 $\rho \in \mathbb{F}$를 잡아서 row에 $t^{k}$ 대신 $\rho^{k}$를 곱하면 결국 $\mathbb{F}$-matrix가 되니 그 determinant는 $\widetilde{O}(n^\omega)$ 시간에 구할 수 있습니다. 이 determinant의 evaluation이 $0$이라면 singular한 것으로 판정하고, 그렇지 않다면 non-singular한 것이 확실히 보장됩니다.

억울하게 determinant를 $0$으로 잘못 판정할 확률을 생각해 보면, 우리가 만든 행렬의 determinant는 최대 $2n - 2$차 다항식이 되므로 많아야 $2n - 2$개의 근을 갖습니다. 잊고 있었던 사실인 $\mathbb{F}$의 원소 개수를 생각하면, 억울하게 root를 고를 확률이 $\frac{2n - 2}{2^{d}}$가 됩니다. Fragment가 최대 $n^2$개이므로, determinant를 사전에 검증할 때 오류가 없을 확률이 $1 - O\left(\frac{n^{3}}{2^{d}}\right)$가 됩니다.

Theorem. 주어진 $\mathbb{E}$-matrix의 permanent를 $\widetilde{O}(n^{2 + \omega})$ 시간에, error probability $O\left(\frac{n^3}{2^d}\right)$ 로 구할 수 있다. $\square$

Determinant는 간단하게 구할 수 있으니 생략합니다. 이제 permanent와 determinant의 차이의 절반, 우리가 원하는 다항식의 evaluation을 계산할 수 있습니다.

Selection of parameters, Implementation

$d = \lceil 5 \log n \rceil$로 설정합니다. 이 때 $\lvert\mathbb{F}\rvert = \Omega(n^5)$가 됩니다. 우리가 오래전에 evaluation을 $n + 1$번 반복하기로 했으니, 이 때의 error probability가 $n \cdot O\left(\frac{n^3}{n^5}\right) = O(n^{-1})$이 됩니다. 따라서, 우리는 shortest even cycle을 $\widetilde{O}(n^{3 + \omega})$ 시간에 error probability $O(n^{-1})$으로 구할 수 있습니다.

이 모든 과정을 Github Repository에 SageMath를 이용하여 정리하고 있습니다. 현재는 다소 suboptimal한 부분이 많으니, 관심이 있으신 분께서는 기여해주시면 감사하겠습니다.

References

• Björklund2022: Andreas Björklund, Thore Husfeldt, and Petteri Kaski. 2022. The shortest even cycle problem is tractable. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022). Association for Computing Machinery, New York, NY, USA, 117–130. https://doi.org/10.1145/3519935.3520030
• Arkin1991: Arkin, Esther M., Christos H. Papadimitriou, and Mihalis Yannakakis. “Modularity of cycles and paths in graphs.” Journal of the ACM (JACM) 38.2 (1991): 255-274.
• McCuaig2004: McCuaig, William. “Pólya’s permanent problem.” the electronic journal of combinatorics (2004): R79-R79.
• Yuster1997: Yuster, Raphael, and Uri Zwick. “Finding even cycles even faster.” SIAM Journal on Discrete Mathematics 10.2 (1997): 209-222.
• Robertson1999: Robertson, Neil, Paul D. Seymour, and Robin Thomas. “Permanents, Pfaffian orientations, and even directed circuits.” Annals of mathematics (1999): 929-975.
• Thomassen1992: Thomassen, Carsten. “The even cycle problem for directed graphs.” Journal of the American Mathematical Society 5.2 (1992): 217-229.
• Thomassen1986: Thomassen, Carsten. “Sign-nonsingular matrices and even cycles in directed graphs.” Linear algebra and its applications 75 (1986): 27-41.
• Williams2010: Williams, Virginia Vassilevska, and Ryan Williams. “Subcubic equivalences between path, matrix and triangle problems.” 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 2010.