koosaga's profile image

koosaga

January 4, 2023 00:00

Introduction to APSP Conjecture and BMM Conjecture

algorithm , computational-hardness , competitive-programming

Introduction to APSP Conjecture and BMM Conjecture

이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 “쉽다” (algorithm) 내지는 “어렵다” (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다.

어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 “어려움을 증명하는” 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 “어떠한 문제는 풀 수 없다” 라는 가설을 만들고, 이 문제가 풀렸을 때 다른 문제를 풀 수 있는 알고리즘을 고안하는, 즉 상대적 쉬움 을 보이는 식으로 쉽다 는 논의에 의존하는 방식을 택한다. 가설이 맞으면 그건 그런대로 좋고, 틀리면 즉시 여러 문제에 대해 파급력이 생기기 때문에 그것도 좋다. 이러한 논의를 보통 Reduction 이라고 부른다. 이 중 Polynomial-time reduction은 아주 잘 알려져 있고 대중적으로도 $P=NP$ 의 중요성을 설명하기 위해 자주 인용된다. $P=NP$ 이면 암호 체계가 모두 붕괴한다 같은 논의가 묘사하는 것이 바로 Polynomial-time reduction의 개념이다.

최근 기술 발전에 따라서 알고리즘이 처리하게 되는 데이터들은 기존과 다르게 천문학적인 수준에 도달하였다. 반면에 프로세서의 발전은 물리적 한계에 부딪혀 정체되어 있는 상황이다. 문제가 쉽다 는 경계를 논의할 때 그동안은 다항 시간과 지수 시간 사이를 그 경계로 보는 관점이 우세하였으나, 이제는 선형 시간에 준하는 알고리즘이 아니면 효율적이지 않은 응용이 많다. 즉, 어떠한 문제가 $O(n^{1.5}), O(n^2), O(n^3)$ 보다 빠르게 풀리는지 아닌지가 어려움의 경계선이 될 수 있다는 것이다. 이러한 새로운 관점을 반영한 다항 시간 내의 Reduction 중 가장 파급력있는 것이 APSP Conjecture와 BMM Conjecture이다. 논의된 지 10년 남짓한 분야이지만, 파급력이 PS 분야를 포함하여 아주 크기 때문에 이번 글을 통해 소개하게 되었다.

Chapter 1. APSP Conjecture

방향성 있는, 또한 가중치가 음이 아닌 정수인 그래프가 주어졌을 때, 모든 정점 쌍 간의 최단 경로를 계산하는 문제를 모든 쌍 최단 경로 (All-Pair Shortest Path, APSP) 라고 부른다. 이 문제는 알고리즘 입문 시간에 배우는 정말 잘 알려진 문제이다.

일반적으로 APSP 문제는 Floyd-Warshall 이라는 아주 간단한 $O(n^3)$ 알고리즘을 사용해서 해결하며, Sparse한 그래프에서는 다익스트라 알고리즘을 $n$ 번 호출하면 $O(nm + n^2 \log n)$ 시간에 해결할 수 있다. 현재 State-Of-The-Art (SOTA) 알고리즘은 $O(\frac{n^3}{2^{\Omega{(\sqrt{ \log n } )}}} )$ 의 시간이 소모되는데, $\sqrt{ \log n}$ 항을 $\log n$ 으로 바꿀 수 있다면 이 역시 $O(n^2)$ 였겠지만 그러한 연구는 물론 없다. 이 글에서 논의하는 APSP는 간선의 개수인 $m$ 을 인자로 고려하지 않기 때문에, 소개한 세 알고리즘 중 $O(n^3)$ 보다 다항 시간만큼 빠른 알고리즘은, 즉 $O(n^{2.9999…})$ 시간에 작동하는 알고리즘은 없다. 이를 기반으로 한 추측이 다음과 같다:

APSP Conjecture. 알고리즘이 subcubic 함은 어떠한 $\epsilon > 0$ 에 대해 $O(n^{3 - \epsilon})$ 에 작동함을 뜻한다. APSP를 해결하는 subcubic한 알고리즘은 존재하지 않는다.

1.1 Subcubic reduction and equivalence

APSP Conjecture가 다른 Polynomial-time reduction의 개념을 차용했기 때문에, reduction 의 개념 역시 동일하게 적용된다.

Definition: Subcubic Reduction. $A$ 에서 $B$ 로 가는 Subcubic reduction 이 존재한다는 것은 ($A \leq_{sc} B$) $B$의 Oracle을 반복적으로 호출하는 다음과 같은 알고리즘 $Z$ 가 존재하여, 모든 $\epsilon > 0$ 에 대해 다음 세 성질을 만족하는 $\delta > 0$ 이 존재함을 뜻한다:

  • $A$ 의 모든 인스턴스 $x$ 에 대해 $Z(x)$ 는 $A$ 를 입력 $x$ 에 대해 푼다.
  • $Z$ 는 $O(n^{3-\delta})$ 시간에 작동한다.
  • 모든 $x \in A$ 에 대해 $n_i$ 를 $Z(x)$ 가 $B$ 에 하는 $i$ 번째 Oracle call이라 하자. 이 때 $\sum_i n_i^{3-\epsilon} \le n^{3 - \delta}$ 이다.

Oracle은 $B$ 의 hypothetical한 subcubic algorithm의 구현체 라고 보면 된다. 위 내용이 이해가 안 가면 이해하지 않아도 된다. “$A \leq_{sc} B$ 면 $B$ 가 Subcubic하게 풀릴 시 $A$ 가 Subcubic하게 풀린다” 라고만 이해해도 아무 문제가 없다. 이하는 Reduction 개념을 활용하여 APSP를 중심으로 한 hardness를 정의한다.

Definition: Subcubic equivalent. $A$ 와 $B$가 Subcubic equivalent하다는 것은 $A \leq_{sc} B$, $B \leq_{sc} A$ 를 뜻한다. Definition: APSP-hard. $A$ 가 APSP-hard 함은 $APSP \leq_{sc} A$ 를 뜻한다. Definition: APSP-complete. $A$가 APSP-complete함은 $A$가 APSP와 Subcubic equivalent 함을 뜻한다.

1.2 Variation and classes of APSP Conjecture

APSP Conjecture는 방향성 있는, 또한 가중치가 음이 아닌 정수인 그래프를 가정한다. 이 조건을 각각 완화했을 때, 즉 가중치가 없거나 방향성이 없을 때 문제가 쉬워지는지를 살펴보자.

APSP in undirected graph. Undirected APSP는 APSP-Complete하다 (아래에서 증명할 예정). Theorem 1 (Zwick, 1998) 모든 간선의 가중치 절댓값이 $O(1)$ 이하라면 (즉, 음수 간선 허용) APSP는 $O(n^{2.529})$ 시간에 해결된다. Theorem 2 (Zwick, 1999) 그래프에 방향성이 없고 모든 간선의 가중치 절댓값이 $O(1)$ 이하라면 (즉, 음수 간선 허용) APSP는 $O(n^{\omega})$ 시간에 해결된다. $\omega$ 는 행렬 곱 상수이다. Theorem 3 (Zwick, 1998) $(1 + \epsilon)$-approximate APSP는 $\tilde{O}(\frac{n^{\omega}}{\epsilon})$ 시간에 해결된다.

고로 APSP 자체는 Undirected라고 쉬워지지 않고, 다만 가중치가 작을 경우 $O(n^3)$ 보다 쉬워짐을 알 수 있다. 특히 가중치가 작을 경우 방향성 여부가 복잡도를 바꾸는데, 만약 이 두 문제 사이의 난이도 차이가 존재한다면, 다음과 같은 주장이 가능하다.

Problem (All-Edges Monochromatic Triangle). $n$ 개의 정점을 가진 그래프와, 정수 색이 붙은 간선들이 주어질 때, 각 간선에 대해서 이 간선이 단색 삼각형 (삼각형을 이루는 세 간선의 색이 동일) 에 속하는지 판별하라. Problem (Min-Max Product). 두 행렬 $A, B$ 가 주어질 때, $C_{i, j} = \min_k \max(A_{i, k}, B_{k, j})$ 인 행렬 $C$ 를 계산하라.

Theorem 4 (LPV20) All-Edges Monochromatic Triangle 가 $T(n)$ 에 해결된다면 Unweighted graph의 APSP를 $T(n) \log^2 n$ 에 해결할 수 있다. Theorem 5 (LPV20) Min-Max Product 가 $T(n)$ 에 해결된다면 Unweighted graph의 APSP를 $T(n) \log^2 n$ 에 해결할 수 있다.

이러한 식으로 Subcubic reduction의 개념을 단순히 $n^3$ 이 아닌 $\tilde{O}(n^{\omega}), \tilde{O}(n^{(\omega+2)/3}), \tilde{O}(n^{(\omega + 1) / 2})$ 등 모든 클래스에 대해서 적용할 수 있다.

1.3 Problems equivalent to APSP Conjecture

아래 APSP Conjecture와 Equivalent한 15개의 문제들을 나열한다.

Theorem 6 (출처1) (출처2). 아래 문제들은 모두 subcubic equivalent하다:

  1. The all-pairs shortest paths problem on weighted digraphs (APSP).
  2. The all-pairs shortest paths problem on undirected weighted graphs.
  3. Detecting if a weighted graph has a triangle of negative total edge weight.
  4. Listing up to $n^{3 - \delta}$ negative triangles in an edge-weighted graph, for a fixed $\delta > 0$.
  5. Computing the matrix product over the $(\min, +)$-semiring.
  6. Verifying the correctness of a matrix product over the $(\min, +)$-semiring.
  7. Checking whether a given matrix defines a metric.
  8. Finding a minimum weight cycle in a graph of non-negative edge weights.
  9. The replacement paths problem on weighted digraphs.
  10. Finding the second shortest simple path between two nodes in a weighted digraph.
  11. Finding a maximum subarray of a given matrix.
  12. Radius: $\min_{s \in V} \max_{t \in V} dist(s, t)$ and $\text{argmin}$ resp.
  13. Median: $\min_{s \in V} \sum_{t \in V} dist(s, t)$ and $\text{argmin}$ resp.,
  14. Betweenness Centrality: For all $s, t\in V-{v}$, compute the sum fraction of shortest path between $s, t$ that contains $v$
  15. Check if the given matrix is the correct APSP distance matrix.

Theorem 6을 다 증명하기는 조금 그래서 1, 2, 3, 4, 5만 증명한다.

  • $3 \le_{sc} 1$: 모든 정점을 $D(0, v), D(1, v), D(2, v), D(3, v)$ 와 같이 4개의 복사본으로 나누고, 각 간선 $(u \rightarrow v)$ 에 대해, $D(i, u) \rightarrow D(i + 1, v)$ 로 가는 간선을 추가해 준다. (음수 간선이 아니게 가중치에 큰 수 $M$ 을 더하자.) 이 그래프에서 APSP를 구하고, $D(0, v) \rightarrow D(3, v)$ 로 가는 최단 경로 중 최소가 $3M$ 이하인지를 확인하면 된다.
  • $4 \le_{sc} 3$: Theorem 6.1
  • $5 \le_{sc} 4$: Theorem 6.2
  • $1 \le_{sc} 5$: $A_{i, i} = 0$ 으로 두고 Repeated squaring을 $\log n$ 번 하면 된다.
  • $2 \le_{sc} 1$: 자명
  • $5 \le_{sc} 2$: Theorem 6.3

Theorem 6.1. 음수 삼각형을 subcubic하게 찾을 수 있으면 임의의 $\delta > 0$ 에 대해 $n^{3 - \delta}$ 개의 음수 삼각형을 subcubic하게 찾을 수 있다. Proof. 모든 정점을 $A(v), B(v), C(v)$ 와 같이 3개의 복사본으로 나누고, 각 간선 $(u \rightarrow v)$ 에 대해, $A(u) \rightarrow B(v), B(u) \rightarrow C(v), C(u) \rightarrow A(v)$ 로 가는 간선을 추가해 준다. 원래 그래프의 삼각형은 이 그래프의 삼각형에 대응되며 모든 삼각형은 $A, B, C$ 에서 정확히 한 점 씩을 지난다. $(A, B, C)$ 집합에 있는 $K$ 개의 음수 삼각형을 분할 정복으로 구한다. $A = A_L \cup A_R, B = B_L \cup B_R, C = C_L \cup C_R$ 과 같이 각각 이분할하고, 총 8가지 분기에 대해서, 해당 분기에 음수 삼각형이 존재하고 (subcubic하게 계산 가능) 아직 $K$ 개의 요구사항을 채우지 못했다면 해당 분기로 내려가서 재귀적으로 계산한다. $T(n) = O(n^{3-\epsilon})$ 이 음수 삼각형을 찾는데 드는 시간이라 하면, 분할 정복의 $D$ 번 level 에서 수행하는 연산 수 합은 다음과 같다 (등호관계가 아니지만 가독성을 위해 추가).

$\sum_{D \le \log_2 N} \min(K, 2^{3D}) T(\frac{n}{2^{D}}) \=\sum_{2^{3D} \le K} 2^{3D} T(\frac{n}{2^{D}}) + \sum_{K < 2^{3D}, D \le \log_2 N} K (\frac{n}{2^{D}})^{3 - \epsilon} \=\sum_{2^{3D} \le K} 2^{3D} T(\frac{n}{2^{D}}) + K (\frac{n}{K^{1/3}})^{3 - \epsilon} \=\sum_{2^{3D} \le K} 2^{3D} T(\frac{n}{2^{D}}) + n^{(3 -\delta)1/3\epsilon} n^{3 - \epsilon} \=\sum_{2^{3D} \le K} 2^{D \epsilon} n^{3 - \epsilon} + n^{(3 -\delta)1/3\epsilon} n^{3 - \epsilon} \= n^{(3 -\delta)1/3 \epsilon} n^{3 - \epsilon} + n^{(3 -\delta)1/3\epsilon} n^{3 - \epsilon} \= n^{3 - \ 1/3\delta \epsilon}$ $\blacksquare$

Theorem 6.2. 음수 삼각형 한 개를 subcubic하게 찾을 수 있으면 $(\min, +)$-semiring 에서 행렬 곱을 계산할 수 있다. Proof. $C_{i, j} = \min_k(A_{i, k} + B_{k, j})$ 이니, 모든 $k$ 에 대해 $C_{i, j} \le A_{i, k} + B_{k, j}$ 인 최대 $C_{i, j}$ 를 이분탐색 하면 된다. 고정된 행렬 $C$ 에 대해, $C_{i, j} > A_{i, k} + B_{k, j}$ 인 $k$의 존재성을 모든 $(i, j)$에 대해서 subcubic하게 판별할 수 있다면, $C$ 는 Parallel binary search의 요령으로 구할 수 있다. 고로 요점은 세 행렬 $A, B, C$ 가 있을 떄 모든 $(i, j)$ 에 대해 $C_{i, j} > A_{i, k} + B_{k, j}$ 인 $k$ 가 존재하는지를 subcubic하게 알아내는 것이다. 이는 다음과 같이 할 수 있다.

그래프 $G$ 를 다음과 같이 구성한다:

  • 정점은 $v_1, v_2, v_3$ 와 같이 $3n$ 개 존재한다 ($1 \le v \le n$).
  • $i_1 - j_2$ 를 잇는 가중치 $A[i, j]$ 의 간선을 추가한다.
  • $i_2 - j_3$ 를 잇는 가중치 $B[i, j]$ 의 간선을 추가한다.
  • $i_3 - j_1$ 를 잇는 가중치 $-C[i, j]$ 의 간선을 추가한다.
$A = {v_1 v\in[n]}, B = {v_2 v\in[n]}, C = {v_3 v\in[n]}$ 이라 하자. 각 집합을 $t$ 개의 조각으로 분할하고, 각 $t^3$ 개의 인스턴스에 대해서 $A_i \cup B_j \cup C_k$의 induced subgraph에서 음수 사이클을 하나 찾는다. 만약 음수 사이클이 있다면, 해당 사이클이 지나는 $-C[i, j]$ 의 간선은 원하는 부등식을 만족하지 않는다. 해당 간선을 지우고 (모든 $t^3$ 개의 인스턴스에 대해 - 정확히는 $t$ 개의 인스턴스겠지만 - 전역적으로 지운다), 음수 사이클이 나올때까지 이를 반복한다.

이 알고리즘의 정당성은 쉽게 볼 수 있다. 이 알고리즘의 시간 복잡도는 어떨까? 알고리즘은, 각 인스턴스에 대해서 한 번 음수 사이클을 찾고, 만약 이 과정에서 간선을 지웠다면 이를 반복한다. 즉, (인스턴스 개수) + ($i_3 - j_1$ 을 잇는 간선) 의 합이 알고리즘이 음수 사이클 Oracle을 호출하는 횟수이다. $D(n)$ 을 음수 사이클을 찾는 데 드는 시간이라고 하면, 시간 복잡도는 $O((n^2 + t^3)D(n / t))$ 이다. $t = n^{2/3}$ 으로 두면 이는 $O(n^2 D(n^{1/3}))$ 이 된다. 고로 $D$ 가 subcubic하다면, 행렬 곱도 subcubic하다.

Theorem 6.3. Undirected APSP를 subcubic하게 해결할 수 있으면 $(\min, +)$-semiring 에서 행렬 곱을 계산할 수 있다. Proof. $M$ 을 아주 큰 수라 하자. 무방향 그래프 $G$ 를 다음과 같이 구성한다:

  • 정점은 $v_1, v_2, v_3$ 와 같이 $3n$ 개 존재한다 ($1 \le v \le n$).
  • $i_1 - j_2$ 를 잇는 가중치 $M + A[i, j]$ 의 간선을 추가한다.
  • $j_2 - k_3$ 를 잇는 가중치 $M + B[i, j]$ 의 간선을 추가한다.

$M$ 이 아주 크기 때문에 $i_1 - k_3$ 을 잇는 경로는 정확히 두 개의 간선을 사용한다. 고로 $C[i, j] = dist(i_1, k_3) - 2M$ 이다.

Chapter 2. Boolean Matrix Multiplication Conjecture

Boolean Matrix Multiplication Conjecture (BMM Conjecture) 는 다음과 같다:

BMM Conjecture. 덧셈이 $\lor$, 곱셈이 $\land$ 로 정의되는 두 불리언 행렬을 곱하는 조합적인 (combinatorial) subcubic한 알고리즘은 존재하지 않는다.

BMM Conjecture는 APSP Conjecture만큼 여러 방면으로 활용할 수 있다는 점에서 중요하다. 특히 배우는 입장에서는 “조합적인” 이라는 정의가 논란의 여지가 많기 때문에 오히려 더 주목해야 할 가설이라고 생각한다.

“조합적” 이라는 단서가 없다면 BMM Conjecture는 성립하지 않는다. 불리언 배열이 아닌 단순 정수 배열로 간주한 후 $O(n^{\omega})$ 시간의 행렬 곱 알고리즘을 사용하고, $C_{i, j} > 0$ 여부로 답을 판별하면 되기 때문이다. 고로 조합적 알고리즘의 정의가 중요할 것인데, 이에 대한 설명을 원 논문에서 그대로 가져오면 다음과 같다.

The notion of a “combinatorial” algorithm does not have a formal definition. Intuitively, such algorithms are not only theoretically but also practically efficient. In the above theorem, by combinatorial we mean an algorithm with low leading constants. One can verify that the reductions in our article have low leading constants and low overhead; hence, any simple fast triangle algorithm would yield a simple (and only slightly slower) BMM algorithm.

간단히 말해, 조합적인 알고리즘은 Strassen 류의 행렬곱을 사용하지 않은, 즉 행렬곱이 $\Omega(n^3)$ 인 세계관의 알고리즘을 뜻한다. 이러한 정의가 나오게 된 배경은 다음과 같이 추정된다.

  • 이 분야에 있는 알고리즘들 중 $n^2$ 보다 느리고 $n^3$ 보다 빠른 거의 모든 알고리즘들은 Strassen 류 빠른 행렬곱 ($O(n^{\omega})$) 에 기반해 있다. 한편으로, Strassen에 기반한 subcubic한 행렬 곱 알고리즘을 효율적으로 구현하려는 시도가 정말 많았지만, 이 중 성공적인 사례는 없었고, 현재 기술 발전 경향성에 미루어봐 앞으로도 성공적일 가능성이 없을 것이다.
    • 행렬이 1000 정도를 넘어가면 Strassen이 몇배 정도 빠르긴 하다. 하지만 성공이라고 볼 수준이 아니며, 그나마도 $O(n^{2.8})$인 Strassen 한정의 이야기이다. 행렬 곱은 오래된 문제고, 단순하면서, 좋은 구현에 걸려있는 보상이 엄청난 문제이기 때문에, 무어의 법칙까지 끝나버린 2020년대의 관점에서는 그냥 알고리즘 자체에 결함이 있다고 보는 것이 합리적이다.
  • 이러한 상황에서 우리가 Strassen은 생각하지 말자 라고 깔끔하게 정리한다면, 우리는 Subcubic hardness를 증명하는 더 강한 도구를 얻을 뿐만 아니라 퇴행적 연구에 인적자원을 낭비하지 말자는 지침을 만들 수 있다. 이는 학계 전체에 유익하다.
  • 어쨌든 BMM Conjecture는 가설일 뿐이다. 가설은 엄밀할 필요가 없다.

이와 별개로 조합적 이라는 전제를 빼더라도 $O(n^3)$ 이 $O(n^{\omega})$ 로 바뀌는 것 외에는 큰 차이가 없다. 어쨌든 BMM을 해결하는 non-combinatorial $\tilde{O}(n^2)$ 알고리즘이 있는 것은 아니기 때문이다. 본인이 알고 있는 BMM reduction 중 $O(n^{\omega})$ 이상의 시간을 쓰는 reduction 역시 들어본 적이 없다.

BMM Conjecture는 APSP Conjecture와 독립적이다. APSP가 반증되더라도 BMM은 반증되지 않을 수 있으며 (APSP를 조합적이지 않은 알고리즘으로 해결) BMM이 반증되더라도 APSP가 반증되지 않을 수 있다 (BMM으로 APSP 해결 불가능). 다만 두 가설은 밀접한 관계를 가지고 있는데, 다음 문제가 APSP-Complete이기 때문이다.

Min-plus matrix multiplication. 덧셈이 $\min$, 곱셈이 $+$ 로 정의되는 두 불리언 행렬을 곱하는 것은 APSP-hard 이다.

$(\min, +)$ 에서의 행렬 곱을 불리언에서 하는 것이 $(\lor, \land)$ 에서의 행렬 곱이고 BMM임을 관찰할 수 있다. 실제로 위와 같은 이유로 APSP에서 사용하는 Reduction이 그대로 BMM에서도 적용되는 경우가 많다.

현재 BMM을 해결할 수 있는 가장 효율적인 조합적 알고리즘은 $O(n^3 poly (\log \log n) / \log^4 n)$ 에 작동한다. 해당 알고리즘은 Strassen과 특별히 관련 없지만, 그다지 practically efficient해 보이지는 않는다. 본인은 BMM Conjecture의 주장에 큰 문제가 없고 좋은 연구 방향이라고 보는데, 다양한 의견이 있을 수 있다고 생각한다. BMM Conjecture가 옳은 연구 방향인지 내지는 적절한지에 대해서는 독자들도 찬성/반대 두 측면 모두에서 직접 고찰해 보면 좋을 것 같다.

2.2 Problems equivalent to BMM Conjecture

아래 BMM Conjecture와 Equivalent한 4개의 문제들을 나열한다.

Theorem 7 (출처1). 아래 문제들은 모두 subcubic equivalent하다:

  1. Boolean matrix multiplication (BMM).
  2. Detecting if a graph has a triangle.
  3. Listing up to $n^{3 - \delta}$ triangles in a graph, for a fixed $\delta > 0$.
  4. Verifying the correctness of a matrix product over the Boolean semiring

Theorem 7의 증명은 Theorem 6 증명을 그대로 사용하면 된다. $\blacksquare$

Chapter 3. Other Conjectures

3.1 Problems equivalent to Diameter

그래프의 지름 (diameter) 는 모든 정점 쌍 $s, t \in V$ 간의 거리 최댓값이다. 즉, $\max_{s, t \in V} dist(s, t)$ 라고 할 수 있다. 지름은 APSP보다 쉬운 문제이지만, 지름이 APSP-Complete 한지는 알려져 있지 않으며 그렇다고 Subcubic한 알고리즘이 알려진 것도 아니다. 특정한 문제들은 Diameter와의 subcubic equivalence를 보일 수 있음이 알려져 있다:

Theorem 8. 아래 문제들은 모두 subcubic equivalent하다:

  1. Diameter of an directed weighted graph.
  2. Positive Betweenness Centrality: Determine if the Betweenness Centrality of $v$ is positive.
  3. Reach Centrality of $v$: $\max_{s, t \in V, dist(s, t) = dist(s, v) + dist(v, t) } \min (dist(s, v), dist(v, t))$

이 글에서는 위 Theorem을 모두 증명하지는 않고, 1번 문제와 2번 문제의 subcubic equivalence만 증명한다. (공교롭게도 Appendix로 뺀 증명을 빼고 처음으로 소개하는 subcubic reduction 증명인데, 어렵지 않아서 입문 용으로도 적절하다고 생각한다.)

Proof of Equivalence for 1 and 2.

  • $\text{Diameter} \le_{sc} \text{PosBetCent}$: PosBetCent를 푸는 Oracle이 있다고 하자. 그림과 같이 새로운 정점 $x$ 를 만든 후 모든 다른 정점을 $x$ 와 거리 $D$ 의 간선으로 잇는다. 만약 $2D$ 보다 지름이 작다면, 어떠한 최단 경로도 $x$ 를 지나지 않을 것이고, $2D$ 이상의 지름을 가진다면, 그 정점 쌍은 $x$ 를 지날 것이다. 고로 PosBetCent를 푸는 Oracle을 사용하여 지름을 이분탐색하면 된다.
  • $\text{PosBetCent} \le_{sc} \text{Diameter}$:
    • 우리는 $dist(s, t) = dist(s, x) + dist(x, t)$ 를 만족하는 $s, t \in V - {x}$ 를 찾으려 한다. $M = \max_{e\in E} w_e, U = 3M V $ 라고 두자. 모든 정점 $v \in V$ 에 대해 $dist(v, x), dist(x, v)$ 를 계산한다. 이는 Dijkstra 두 번으로 되니 $O(n^2)$ 에 해결된다.
    • 이제 다음과 같은 그래프를 구성한다:
    • $3 V - 2$ 개의 정점: $V \cup {v_a v \in V - {x}} \cup {v_b v \in V - {x}}$. $x$ 를 제외한 모든 정점이 3개로 복제된다.
    • $ E + 4 V - 2$ 개의 간선
      • 원래 간선.
      • 모든 $v \in V - {x}$에 대해 $v_a \rightarrow v$ 로 가는 가중치 $U - dist(v, x)$ 의 간선을 잇는다.
      • 모든 $v \in V - {x}$에 대해 $v \rightarrow v_b$ 로 가는 가중치 $U - dist(x, v)$ 의 간선을 잇는다.
      • 모든 $v \in V$에 대해 $v \rightarrow v_a$ 로 가는 가중치 $0$ 의 간선을 잇는다.
      • 모든 $v \in V$에 대해 $v_b \rightarrow v$ 로 가는 가중치 $0$ 의 간선을 잇는다.
    • 어떠한 $v_a$ 에서 시작하여 $v_b$ 에서 끝나야 한다. 그 형태를 $s_a \rightarrow s \rightarrow t \rightarrow t_b$ 라 하자. 이 때의 지름은 $2U - dist(s, x) - dist(x, t) + dist(s, t) = 2U - (dist(s, x) + dist(x, t) - dist(s, t))$ 이다. 이 값은 삼각부등식에 의해 최대 $2U$ 여야 한다. 등식이 성립한다면 정의에 의해 PosBetCent가 참이다.

특정한 문제들은 APSP, 3SUM, SETH 중 하나의 추측만 맞아도 풀 수 없는 경우가 있다. 이러한 경우 해당 문제를 효율적으로 해결하기 위해서는 APSP, 3SUM, SETH 이 모두 거짓이어야 하고 이는 단순 APSP보다 훨씬 더 믿기 힘든 결과이다. 놀랍게도, Dynamic graph algorithm 문제 중에서 이러한 종류의 문제가 상당수 존재한다.

Theorem 9 (AWY14). APSP, 3SUM, SETH 중 하나 이상의 추측이 맞다면, 아래 문제들은 업데이트/쿼리 시간이 amortized $n^{1 - o(1)}$ 여야 하거나, 전처리 시간이 $n^{3 - o(1)}$ 이어야 한다:

  • 방향 그래프, 간선 추가/제거, SCC 개수.
  • 방향 그래프, source node, 간선 추가/제거, $s$에서 도달 가능한 노드 개수.
  • 무방향 그래프, source node, 정점 on/off, $s$에서 도달 가능한 노드 개수.
  • 무방향 그래프, 간선이 $n$ 이하 양의 정수 가중치, source node, sink node, 간선 추가/제거, 최대 유량

Theorem 9의 증명은 APSP, 3SUM, SETH를 가정하면 아래 문제를 $O(n^{3 - \epsilon})$ 에 풀 수 없다는 정리에서 시작된다:

Problem (Triangle-Collection). 정점에 색이 칠해진 그래프 $G$ 가 주어졌을 때, 모든 서로 다른 색 트리플렛 $a, b, c$ 에 대해서 $x$는 색 $a$, $y$ 는 색 $b$, $z$ 는 색 $c$ 를 가지는 삼각형 $(x, y, z)$ 가 항상 존재하는지 여부를 판별하라.

각 추측에서 이 문제를 유도하고, 이후 중간과정을 몇개 거치면 위와 같은 Dynamic Problem의 hardness를 얻을 수 있다. 논문의 내용이 길고 꽤 어렵기 때문에 여기서는 추가 설명을 생략한다.

같은 논문에는 다음과 같은 Theorem도 존재한다: Theorem 10 (AWY14). SETH를 가정하면, 간선이 $O(n)$ 개인 그래프에서 single-source all-sink max flow를 $O(n^{2 - \epsilon})$ 시간에 해결할 수 없다.

최근의 Almost-Linear Max Flow 연구에 의해 Max Flow는 Naive하게 $O(n^{1 + o(1)})$ 시간에 계산할 수 있는데, static graph에서 source/sink 쿼리를 하더라도 Naive보다 빠를 수 없고, static source/sink 에서 간선 업데이트 쿼리를 하더라도 Naive보다 빠를 수 없으니, Directed graph에서는 Max Flow에 연관된 Dynamic problem이 풀릴 가능성이 적음을 엿볼 수 있다.

Chapter 4. Hardness for range query problems

이 단락에서는 위에서 배운 APSP와 BMM Conjecture를 사용하여 우리가 PS에서 다룰 법한 자료구조 문제들의 Hardness를 보이는 것을 목표로 한다. 독립적인 알고리즘들을 공부한 다른 글들에서도 이러한 Hardness를 조사한 글들이 있을 정도로 PS와 연관이 깊은 주제이다. 해당 글들도 읽어보면 꽤 도움이 되며, 특히 Aeren 님이 작성해 주신 Data Structures for Range Mode Query 글의 접근법은 이번 글에서도 다시 사용할 것이다.

또한 추가적으로 이 분야에 대해서 공부하고 싶다면 Equivalences between triangle and range query problems 를 읽어 보는 것도 좋다.

첫 번째 문제는 흔히 2D 세그먼트 트리에서 Lazy propagation이 안 되는 이유 로 잘 알려진 증명이다.

문제 1. 다음과 같은 쿼리 문제를 생각해 보자:

  • 초기화: 크기 $n \times n$의 행렬 $A$
  • 쿼리 1: $(i, l, r, x)$ 가 주어질 때, $A[i][j] = A[i][j] + x$ 를 모든 $l \le j \le r$ 에 대해 처리. 최대 $O(n^2)$ 번 주어짐.
  • 쿼리 2: $(l1, r1, l2, r2)$ 가 주어질 때, $\max_{i \in [l1, r1], j \in [l2, r2]} A[i][j]$ 를 계산. 최대 $O(n^2)$ 번 주어짐.

Theorem 11.1. APSP Conjecture 하에서 문제 1을 $O(n^{3 - \epsilon})$ 에 해결하는 알고리즘은 존재하지 않는다. Proof. 위와 같은 쿼리를 해결하는 oracle이 있다고 하자. 일반성을 잃지 않고, 쿼리 2가 최솟값을 계산한다고 가정한다 (부호 뒤집으면 됨.) $n \times n$ 행렬 $A, B$ 가 있다고 할 때, 다음과 같이 두 행렬의 min-plus 곱을 계산한다.

  • 자료 구조를 $B$ 로 초기화하고, $C$ 의 각 행에 대해서 따로 계산한다. 편의상 $C_{1, i}$ 만 계산한다고 하자.
  • $C_{1, i} = \min_{k} (A_{1, k} + B_{k, i})$ 이다.
  • $n$ 번의 쿼리 1 호출을 통해서, 자료 구조의 $k$ 번 행에 $A_{1, k}$ 를 더한다.
  • $C_{i, 1}$ 은 $i$ 번 열의 최솟값이니 $n$ 번의 쿼리 2 호출로 계산한다.
  • $n$ 번의 쿼리 1 호출을 통해서, 자료 구조의 $k$ 번 행에 $-A_{1, k}$ 를 더하여 원상태로 복귀한다.

이를 모든 $i$ 에 대해 반복하면 Min-plus 곱을 $O(n^{3 - \epsilon})$ 에 계산할 수 있다.

두 번째 문제는 Merge sort tree에 Lazy propagation이 안 되는 이유를 설명한다.

문제 2. 다음과 같은 쿼리 문제를 생각해 보자:

  • 쿼리 1: $(l, r, x)$ 가 주어질 때, $A[i] = A[i] + x$ 를 모든 $l \le i \le r$ 에 대해 계산하라. 최대 $O(n)$ 번 주어짐.
  • 쿼리 2: $x$ 가 주어질 때, $x$ 이하의 값의 개수를 계산하라. 최대 $O(n)$ 번 주어짐.

Theorem 11.2. APSP Conjecture 하에서 문제 1을 $O(n^{1.5 - \epsilon})$ 에 해결하는 알고리즘은 존재하지 않는다. Proof. 위와 같은 쿼리를 해결하는 oracle이 있다고 하자. 문제 1과 거의 비슷한 접근을 사용한다. $n \times n$ 행렬 $A, B$ 가 있다고 할 때, 다음과 같이 두 행렬의 min-plus 곱을 계산한다. 모두 1-based로 서술한다.

  • 자료 구조의 $(i-1)n + j$ 번 원소를 $B[i][j] + j M$ 으로 초기화하자. $M$ 은 충분히 큰 수이다.
  • $C$ 의 각 행에 대해서 따로 계산한다. 편의상 $C_{1, i}$ 만 계산한다고 하자.
  • $n$ 번의 쿼리 1 호출을 통해서, 자료 구조의 $[nk-n+1, nk]$ 구간에 $A_{1, k}$ 를 더한다.
  • $C_{i, 1}$ 은 $kn + i$ 번 원소들의 최솟값이다. $X + jM$ 이하의 원소를 세면, $A_{1, k} + B_{k, j} \le X$ 인 원소 $k$ 의 개수, 그리고 $(j - 1)n$ 개의 원소가 세어질 것이다. 이 값이 $(j-1)n + 1$ 인 최소 $X$ 를 이분 탐색하면 $\min_k A_{1, k} + B_{k, j}$ 를 계산할 수 있다. $n \log X$ 번의 쿼리를 사용한다.
  • $n$ 번의 쿼리 1 호출을 통해서, 자료 구조의 $[nk-n+1, nk]$ 구간에 $-A_{1, k}$ 를 더하여 원상태로 복귀한다.

이를 모든 $i$ 에 대해 반복하면 Min-plus 곱을 $O(n^{3 - \epsilon})$ 에 계산할 수 있다.

세 번째 문제는 Aeren이 소개한 Range Mode Query의 작은 변형으로, 원 증명과 유사한 방법으로 증명된다.

문제 3. 다음과 같은 쿼리 문제를 생각해 보자:

  • 초기화: 크기 $n$의 배열 $A$
  • 쿼리 1: $(l, r, x)$ 가 주어질 때, $A[l], A[l + 1], \ldots, A[r]$ 에서 정확히 $x$ 번 등장하는 원소 $c$ 의 개수를 계산하라. 최대 $O(n)$ 번 주어짐.

Theorem 11.3. BMM Conjecture 하에서 문제 3를 $O(n^{1.5 - \epsilon})$ 에 해결하는 조합적 알고리즘은 존재하지 않는다. Proof. Range Mode Query의 접근법을 활용한다. 위와 같은 쿼리를 해결하는 oracle이 있다고 하자. $n \times n$ 불리언 행렬 $A, B$ 가 있다고 할 때, 다음과 같은 $n^2$ 크기의 배열 두 개를 만든다:

  • $L$ 은 $n$ 개의 길이 $n$ 의 Permutation $L_i$ 를 순서대로 붙여서 만든다. $A_{i, j} = 1$ 인 원소가 $k_i$ 개라고 하면, $L_i$ 의 앞 $n - k_i$ 개 원소들은 $A_{i, L_{i, j}} = 0$, 뒤 $k_i$ 개 원소들은 $A_{i, L_{i, j}} = 1$ 을 만족한다.
  • $R$ 은 $n$ 개의 길이 $n$ 의 Permutation $R_i$ 를 순서대로 붙여서 만든다. $B_{j, i} = 1$ 인 원소가 $m_i$ 개라고 하면, $R_i$ 의 앞 $m_i$ 개 원소들은 $B_{R_{i, j}, i} = 1$, 뒤 $n - m_i$ 개 원소들은 $B_{R_{i, j}, i} = 0$ 을 만족한다.

이제 위의 oracle에 $L + R$ 을 넣어 initialize한다. 우리는 모든 $i, j$ 에 대해 $A_{i, k} = 1, B_{k, j} = 1$ 을 만족하는 $k$ 가 존재하는지 여부를 찾고 싶다. $L_i$ 의 뒤 $k_i$ 개 원소와 $R_j$ 의 앞 $m_j$ 개 원소 중 교집합이 있다면, 달리 말해 두 번 등장하는 원소가 존재한다면, 이러한 $k$ 가 존재한다고 볼 수 있다. $L_i$ 의 뒤 $k_i$ 개 원소와 $R_j$ 의 앞 $m_j$ 개 원소를 포함하는 구간을 $A$ 에서 잡으면, 그 사이에는 몇 개의 permutation이 있을 것이다. 몇 개인지는 쉽게 셀 수 있고, 그 안에서는 등장 횟수가 모두 동일하니. 그 안에 들어가는 permutation의 개수 $+2$ 번 등장하는 원소가 1개 이상 존재하는지 아닌지를 판별하면 된다. 고로 oracle을 통해 $O((n^2)^{1.5-\epsilon})$, 즉 subcubic time에 BMM을 조합적으로 해결할 수 있다. $\blacksquare$

네 번째 문제는 갱신 없는 배열이 주어질 때 구간의 반전 수 (inversion) 을 구하는 문제이다. 흔히 Mo’s algorithm을 사용하여 구하는 풀이가 잘 알려져 있으며, 온라인 저지 에서도 찾을 수 있다.

문제 4. 다음과 같은 쿼리 문제를 생각해 보자:

  • 초기화: 크기 $n$의 배열 $A$
  • 쿼리 1: $(l, r)$ 가 주어질 때, $l \le i < j \le r$ 이며 $A[i] > A[j]$ 인 $(i, j)$ 쌍의 수를 계산하라. 최대 $O(n)$ 번 주어짐.

Lemma. 문제 4 를 $O(n^{1.5 - \epsilon})$ 에 해결하는 조합적 알고리즘이 존재하면, 다음 문제를 $O(n^{1.5 - \epsilon})$ 에해결하는 조합적 알고리즘이 존재한다.

문제 4.1.

  • 초기화: 크기 $n$의 배열 $A$
  • 쿼리 1: $(l, r)$ 가 주어질 때, $l \le i < j \le r$ 이며 $A[i] = A[j]$ 인 $(i, j)$ 쌍의 수를 계산하라. 최대 $O(n)$ 번 주어짐.

Proof of Lemma. 배열 $A$ 가 주어졌을 때, 다음과 같은 순열 $P_1, P_2$ 를 차례대로 만든다. 이 과정은 $O(n \log n)$ 에 가능하다.

  • $P_1(i) < P_1(j)$ 는 $A_i < A_j$ 거나 $A_i = A_j, i < j$ 임과 동치
  • $P_2(i) < P_2(j)$ 는 $A_i < A_j$ 거나 $A_i = A_j, i > j$ 임과 동치

한 마디로, $P_1$ 은 $(A_i, i)$ 를 좌표압축한 것이고, $P_2$ 는 $(A_i, -i)$ 를 좌표압축한 것이다. 이후 문제 4를 해결하는 Oracle을 두 개 만든 후 각각을 $P_1, P_2$ 로 초기화한다. $l \le i < j \le r$ 에 대해서, $A_i \neq A_j$ 일 경우 두 Oracle 에서 동일하게 inversion으로 세거나 세지 않는다. $A_i = A_j$ 일 경우 $P_1$ 에서는 inversion으로 세지 않고, $P_2$ 에서는 inversion으로 센다. 쿼리 1을 처리할 때, $P_2$ 의 $(l, r)$ 쿼리 반환 값에서 $P_1$ 의 $(l, r)$ 쿼리 반환 값을 뺀 것을 반환하면 된다. $\blacksquare$

Theorem 11.4. BMM Conjecture 하에서 문제 4를 $O(n^{1.5 - \epsilon})$ 에 해결하는 조합적 알고리즘은 존재하지 않는다.

Proof. 문제 4를 해결하는 Oracle이 있다고 하자. Lemma에 의해 문제 4.1을 해결하는 Oracle도 존재한다. $n \times n$ 불리언 행렬 $A, B$ 가 있다고 할 때, Theorem 11.3과 동일하게 $L, R$ 을 구성하고 초기화하며 쿼리도 동일하게 한다. 모든 수의 등장 횟수는, 만약 Full block의 개수가 $X$ 개라면

  • 기본적으로 full block의 개수 $X$만큼 등장한다.
  • full block에서 삐져나온 suffix, prefix는 $X + 1$만큼 등장
  • 겹치는 원소들은 $X + 2$만큼 등장 (이러한 원소의 수를 $c$라 하자)

$z = k_i + m_j$ 라 하면, $X + 1$ 번 등장하는 원소는 $z - 2c$ 개, $X$ 번 등장하는 원소는 $n - (z - 2c + c) = n - z + c$ 개이다. 이에 따라, 쿼리의 반환 결과는 $c\frac{X(X+1)}{2} + (z-2c)\frac{(X+1)X}{2} + (n-z+c)\frac{X(X-1)}{2}$ 이 된다. 이를 정리하면

$z\frac{(X+1)X}{2} + (n-z)\frac{X(X-1)}{2} + c$

가 된다. 여기서 $z, X, n$ 은 모두 아는 수이기 때문에 $c$ 를 역산할 수 있다. $c > 0$ 이면 $C_{i, j} > 0$ 이니, subcubic time에 BMM을 조합적으로 해결할 수 있다. $\blacksquare$