Hardness for APIO 2019 Bridge

2019년 APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한 번 생각해 봐야 할 것 같다.

문제를 요약하면 다음과 같다. (원래 문제에서는 트리가 아니라 그래프가 주어지지만, 여기서는 트리라고 가정하고 Hardness를 증명한다. 즉, 문제 상황보다 더 강한 증명이다.)

• 크기 $n$ 의 가중치 있는 트리가 주어졌을 때, 다음 두 연산을 처리하여라:
  • $Update(e, w)$: 간선 $e$ 의 가중치를 $w$ 로 갱신한다.
  • $Query(v, x)$: 정점 $v$ 에서 가중치 $x$ 이하인 간선만 사용해서 도달할 수 있는 정점의 수를 계산하라.

모든 쿼리는 온라인으로 처리해야 한다고 하자. 다음과 같은 Conjecture를 가정한다.
Conjecture (OMv Conjecture). $n \times n$ Boolean matrix와 vector $v_1, v_2, \ldots, v_n$ 이 주어졌을 때, $M v_1, M v_2, \ldots, M v_n$ 을 계산하여라. 이 때 $v_i$ 는 $M v_{i-1}$ 을 계산한 후에만 얻을 수 있다 (Online). 이 문제는 $O(n^{3-\epsilon})$ 에해결하는 것이 불가능하다.

다음 Theorem이 성립한다. (Marek Sokołowski가 증명을 제공해 주었다.)

Theorem. APIO 2019 Bridges를 $T(n), U(n), Q(n)$ 시간에 초기화 / 업데이트 / 쿼리 할 수 있을 때, OMv 문제를 $T(n^2) + n (U(n) + Q(n))$ 에 해결할 수 있다.
Proof. 1-based로 표기한다. $n \times (n + 2)$ 개의 정점을 가진 트리를 구성하자. 트리의 각 정점은 $n \times (n + 2)$ 형태의 격자로 배치되어 있다. $i$ 번 행 에는 길이 $n+1$ 의 경로가 있는데:

• 모든 $1 \le j \le n$ 에 대해 $(i, j+1) - (i, j+2)$ 를 잇는 간선의 가중치는 $1 - M[j][i] + 2j$
• $(i, 1) - (i, 2)$ 를 잇는 간선의 가중치는 $v[i] = 1$ 이면 $0$, $v[i] = 0$ 이면 $\infty$
  그리고 $(i, 1) - (i+1, 1)$ 을 잇는 간선의 가중치를 $\infty$ 로 둔다. $(1 \le i \le n-1)$.

$S = \sum_j v_j$, $w_i = \sum M_{i, j} v_j$ 라고 하자 (mod 2전의 값). 모든 $1 \le k \le n$ 에 대해, $Query((1, 1), 2k) = n + kS + w_{k}$ 가 성립한다. 고로, 각 $v$ 에 대해서 위와 같이 $(i, 1) - (i, 2)$ 의 간선 가중치를 업데이트 한 후 $n$ 번의 쿼리로 곱을 계산할 수 있다.

실제 문제에서는 오프라인 쿼리가 허용되는데, 이 경우에는 OMv 대신 BMM으로 문제가 바뀐다. Combinatorial 조건을 추가하면 동일한 Bound가 그대로 유지된다.