<div id="readability-page-1" class="page"><div>두 $n \times n$ 행렬 $A, B$ 의 Min-Max Product는 $C_{i, j} = \min_k \max(A_{i, k}, B_{k, j})$ 로 정의된다. 만약 이 문제를 $T(n)$ 시간에 해결할 수 있다고 하자. 이전 블로그 글에서 <a href="https://koosaga.com/310">다음과 같은 사실</a>을 소개했다:
Theorem 5. Min-Max Product 가 $T(n)$ 에 해결된다면 Unweighted directed graph의 APSP를 $T(n)\log^2 n$ 에 해결할 수 있다.
Min-Max Product는 현재 $O(n^{(3 + \omega)/2})$ 시간에 해결하는 것이 최적이고, Unweighted APSP는 $O(n^{2.529})$ 시간에 해결하는 것이 최적으로 알고 있다. APSP Conjecture만큼 강하지는 않지만, 아주 오랜 기간동안 $O(n^2)$ 에 준하는 풀이가 알려지지 않은 문제 중 하나이다.
2019년 <a href="https://koosaga.com/232">APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해</a>서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한번 생각해 봐야 할 것 같다. 다음과 같은 사실이 성립하기 때문이다:
Theorem. APIO 2019 Bridges를 $T(n, m, q)$ 에 해결할 수 있다면 Min-Max Product를 $T(n, n^2, n^2 \log n)$ 에 해결할 수 있다. Proof. 일반성을 잃지 않고, 무게가 음수일 수 있다고 하자. (입력에 충분히 큰 수를 더해서 해결) 또한 Min-Max Product가 아닌 Max-Min Product를 계산하자 (Negation으로 해결). 두 행렬 $A, B$ 가 주어질 때, $7n+5$ 개의 정점을 가진 그래프를 만든다.
<ul>
<li>정점 1개는 Source 정점이다. $s$ 로 나타낸다.</li>
<li>Layer 1의 정점 $n$ 개는 $A(1), A(2), \ldots, A(n)$ 으로 나타낸다.</li>
<li>Layer 2의 정점 $n$ 개는 $B(1), B(2), \ldots, B(n)$ 으로 나타낸다.</li>
<li>Layer 3의 정점 $n$ 개는 $C(1), C(2), \ldots, C(n)$ 으로 나타낸다.</li>
<li>정점 1개는 Sink 정점이다. $t$ 로 나타낸다.</li>
<li>Sink 정점과 함께 $4n+3$ 개의 Dummy 정점이 있다.</li>
</ul>
다음과 같이 $O(n^2)$ 개의 간선을 추가한다.
<ul>
<li>$s$ 에서 $A(i)$ 로 $-\infty$ 가중치의 간선을 추가한다.</li>
<li>$A(i)$ 에서 $B(j)$ 로 $A[i, j]$ 가중치의 간선을 추가한다.</li>
<li>$B(j)$ 에서 $C(k)$ 로 $B[j, k]$ 가중치의 간선을 추가한다.</li>
<li>$C(k)$ 에서 $t$ 로 $-\infty$ 가중치의 간선을 추가한다.</li>
<li>$t$ 에서 모든 Dummy 정점으로 $\infty$ 가중치의 간선을 추가한다.</li>
</ul>
이제 $C[i, j]$ 를 다음과 같이 계산한다:
<ul>
<li>$s \rightarrow A(i), C(j) \rightarrow t$ 가중치를 $\infty$ 로 수정한다.</li>
<li>$s$ 에서 $4n+3$ 개 이상의 정점을 방문하는 최대 자동차 무게를 이분 탐색한다 (답의 후보가 $n^2$ 개 이기 때문에 $\log X$ 가 아닌 $\log n$ 번의 쿼리로 충분.)</li>
<li>$s \rightarrow A(i), C(j) \rightarrow t$ 가중치를 $-\infty$ 로 수정한다.</li>
</ul>
Remark. 이 Reduction에서는 모든 쿼리에서 자동차가 출발하는 정점이 고정되어 있다. Remark. APIO 2019 Bridges 문제는 $T(n, m, q) = O(q \sqrt m \log n)$ 시간에 해결할 수 있다. Remark. APIO 2019 Bridges 문제는 $T(n, m, q) = O(qn + m \log^4 n)$ 시간에 해결할 수 있다.</div></div>

구사과

두 $n \times n$ 행렬 $A, B$ 의 Min-Max Product는 $C_{i, j} = \min_k \max(A_{i, k}, B_{k, j})$ 로 정의된다. 만약 이 문제를 $T(n)$ 시간에 해결할 수 있다고 하자. 이전 블로그 글에서 다음과 같은 사실을 소개했다:
Theorem 5. Min-Max Product 가 $T(n)$ 에 해결된다면 Unweighted directed graph의 APSP를 $T(n)\log^2 n$ 에 해결할 수 있다.
Min-Max Product는 현재 $O(n^{(3 + \omega)/2})$ 시간에 해결하는 것이 최적이고, Unweighted APSP는 $O(n^{2.529})$ 시간에 해결하는 것이 최적으로 알고 있다. APSP Conjecture만큼 강하지는 않지만, 아주 오랜 기간동안 $O(n^2)$ 에 준하는 풀이가 알려지지 않은 문제 중 하나이다.
2019년 APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한번 생각해 봐야 할 것 같다. 다음과 같은 사실이 성립하기 때문이다:
Theorem. APIO 2019 Bridges를 $T(n, m, q)$ 에 해결할 수 있다면 Min-Max Product를 $T(n, n^2, n^2 \log n)$ 에 해결할 수 있다.
Proof. 일반성을 잃지 않고, 무게가 음수일 수 있다고 하자. (입력에 충분히 큰 수를 더해서 해결) 또한 Min-Max Product가 아닌 Max-Min Product를 계산하자 (Negation으로 해결). 두 행렬 $A, B$ 가 주어질 때, $7n+5$ 개의 정점을 가진 그래프를 만든다.
정점 1개는 Source 정점이다. $s$ 로 나타낸다.
Layer 1의 정점 $n$ 개는 $A(1), A(2), \ldots, A(n)$ 으로 나타낸다.
Layer 2의 정점 $n$ 개는 $B(1), B(2), \ldots, B(n)$ 으로 나타낸다.
Layer 3의 정점 $n$ 개는 $C(1), C(2), \ldots, C(n)$ 으로 나타낸다.
정점 1개는 Sink 정점이다. $t$ 로 나타낸다.
Sink 정점과 함께 $4n+3$ 개의 Dummy 정점이 있다.
다음과 같이 $O(n^2)$ 개의 간선을 추가한다.
$s$ 에서 $A(i)$ 로 $-\infty$ 가중치의 간선을 추가한다.
$A(i)$ 에서 $B(j)$ 로 $A[i, j]$ 가중치의 간선을 추가한다.
$B(j)$ 에서 $C(k)$ 로 $B[j, k]$ 가중치의 간선을 추가한다.
$C(k)$ 에서 $t$ 로 $-\infty$ 가중치의 간선을 추가한다.
$t$ 에서 모든 Dummy 정점으로 $\infty$ 가중치의 간선을 추가한다.
이제 $C[i, j]$ 를 다음과 같이 계산한다:
$s \rightarrow A(i), C(j) \rightarrow t$ 가중치를 $\infty$ 로 수정한다.
$s$ 에서 $4n+3$ 개 이상의 정점을 방문하는 최대 자동차 무게를 이분 탐색한다 (답의 후보가 $n^2$ 개 이기 때문에 $\log X$ 가 아닌 $\log n$ 번의 쿼리로 충분.)
$s \rightarrow A(i), C(j) \rightarrow t$ 가중치를 $-\infty$ 로 수정한다.
Remark. 이 Reduction에서는 모든 쿼리에서 자동차가 출발하는 정점이 고정되어 있다.
Remark. APIO 2019 Bridges 문제는 $T(n, m, q) = O(q \sqrt m \log n)$ 시간에 해결할 수 있다.
Remark. APIO 2019 Bridges 문제는 $T(n, m, q) = O(qn + m \log^4 n)$ 시간에 해결할 수 있다.

APIO 2019 Bridges is not easier than Undirected Unit APSP

댓글