A game of cops and robbers with helicopter

서론

이전 글에서는 평면그래프에서 Cops and Robber 게임에 대해 다루었다면, 이번 글에서는 일반 그래프에서 새로운 버전의 Cops and Robber 게임에 대해 다룬다. Treewidth라는 개념을 가져와 새로운 버전의 Cops and Robber 게임과 밀접한 관련이 있음을 보인다.

1. Cops and Robber 게임의 규칙

1.1 기본 설정

유한 단순 무방향 그래프 $G$를 고정한다. 정점 집합을 $V(G)$로 표기한다.

정수 $m \ge 1$을 경찰의 수로 둔다. 게임에는 두 플레이어가 있다.

경찰: 동시에 최대 $m$개의 정점을 점유할 수 있다.
도둑: 그래프 상의 한 정점에 위치하며, 경찰이 점유하지 않은 정점들만을 이용해 이동할 수 있다.

경찰은 “동시에 여러 정점에 존재하는 자원”이고, 도둑은 “하나의 정점에 있는 말”로 모델링한다.

1.2 상태의 정의

게임의 한 시점의 상태는 쌍 $(X, R)$로 정의하며, 다음 조건을 만족한다.

$X \subseteq V(G)$, $ X \le m$: 현재 그래프 위에 존재하는 경찰들이 점유하고 있는 정점들의 집합.
$R \in V(G)$: 도둑이 위치한 하나의 정점.
항상 $R \notin X$인 상태만 게임의 유효 상태로 취급한다.
즉, 어떤 시점에 $R \in X$가 되면 그 순간 경찰이 도둑을 잡은 것으로 간주하고 게임은 종료한다.

라운드 $i$에서의 상태를 $(X_i, R_i)$로 쓴다. 여기서 $X_i$는 라운드 $i$ 직후(경찰과 도둑의 이동이 모두 끝난 후)의 경찰 위치 집합, $R_i$는 같은 시점의 도둑 위치를 의미한다.

1.3 한 라운드의 진행

라운드 $i \ge 1$에서, 직전 라운드가 끝난 뒤의 상태가 $(X_{i-1}, R_{i-1})$라고 하자. 이때 항상 $R_{i-1} \notin X_{i-1}$라고 가정한다(그렇지 않으면 이미 이전 라운드에서 경찰이 승리한 상태이다).

라운드 $i$는 다음 세 단계로 진행된다.

경찰의 다음 위치 선언 및 일부 경찰 철수
경찰은 라운드 $i$가 모두 끝난 후 점유하고자 하는 정점들의 집합 $X_i \subseteq V(G)$ 를 선언한다. 이때 $|X_i| \le m$이어야 한다. 이 선언과 동시에, 현재 정점 집합 $X_{i-1}$ 중에서 $X_i$에 포함되지 않는 정점들, $X_{i-1} \setminus X_i$ 에 위치한 경찰들은 즉시 그래프에서 모두 떠난다.

이 단계 직후, 그래프 위에 실제로 남아 있는 경찰들은 $X_{i-1} \cap X_i$에만 존재한다.
도둑의 이동
도둑은 현재 정점 $R_{i-1}$에서 출발하여, 경찰이 계속 점유하고 있는 정점들 $X_{i-1} \cap X_i$ 을 지나지 않고 이동할 수 있다.

형식적으로, 도둑은 어떤 정점 $R_i \in V(G)$를 선택하는데, 다음 조건을 만족해야 한다.
- 도둑은 그래프 $G \setminus (X_{i-1} \cap X_i)$에서 이동한다. 즉, 이동 경로의 모든 정점은 $X_{i-1} \cap X_i$에 속하지 않는다.
- 이 그래프 $G \setminus (X_{i-1} \cap X_i)$ 안에서 $R_{i-1}$와 $R_i$를 잇는 경로가 존재해야 한다.
이 단계에서 도둑은 아직 $X_i \setminus X_{i-1}$에는 경찰이 도착해 있지 않다고 가정하고 움직인다. 따라서 이 정점들을 통과하거나 그 위에 도착하는 것이 허용된다. 다만, 다음 단계에서 경찰이 도착한 뒤 $R_i$가 경찰이 도착한 정점과 일치하면 곧바로 포획된다.
새로운 경찰 도착 및 승리 판정
마지막으로, 경찰이 $X_i \setminus X_{i-1}$의 각 정점으로 이동하여 도착한다. 이 단계가 끝났을 때, 그래프 위에 존재하는 경찰들의 정점 집합은 정확히 $X_i$가 된다.
- 만약 이때 $R_i \in X_i$이면, 도둑과 경찰이 같은 정점에 위치하게 되므로 경찰이 도둑을 잡은 것으로 간주하고 게임은 종료된다.
- 그렇지 않으면, 새로운 상태는 $(X_i, R_i)$가 되며 다음 라운드 $i+1$로 진행된다.

요약하면, 각 라운드에서 경찰은 먼저 다음에 점유할 정점 집합 $X_i$를 선언하여 일부 정점에서 철수하고 일부 정점에 잔류한다. 그 사이 도둑은 잔류 경찰들이 있는 정점 $X_{i-1} \cap X_i$를 피해서 이동하고, 마지막에 새로이 투입되는 경찰들이 $X_i \setminus X_{i-1}$에 도착한다. 어느 시점에서든 상태 $(X_i, R_i)$가 $R_i \in X_i$를 만족하는 순간 경찰이 승리한다.

1.4 승리 전략과 cop number

경찰에게 승리 전략이 존재한다는 것은, 경찰이 어떤 전략 $\sigma$를 선택하면 도둑의 어떤 대응 전략에도 불구하고 유한한 단계 안에 $R_i \in X_i$가 성립하여 경찰이 승리하게 됨을 의미한다.

경찰의 최소 필요 수 $c(G)$를 cop number라 하고, 다음과 같이 정의한다.

$m \ge c(G)$이면 $m$명의 경찰에게 승리 전략이 존재하고,
$m < c(G)$이면 도둑에게 회피 전략이 존재하여 경찰은 도둑을 잡을 수 없다.

2. Treewidth

2.1 tree decomposition의 정의

유한 단순 그래프 $G$를 고정한다. tree decomposition은 다음과 같은 데이터의 쌍 $(T, W)$이다.

$T$: 트리,
$W = (W_t)_{t \in V(T)}$: 각 트리 정점 $t$에 대해 $W_t \subseteq V(G)$인 정점 집합. 각 $W_t$를 bag라고도 부른다.

이때 다음 두 공리를 만족해야 한다.

(W1) $\bigcup_{t \in V(T)} W_t = V(G)$이고 임의의 간선 $uv \in E(G)$에 대해 $\{u, v\} \subseteq W_t$를 만족하는 $t \in V(G)$가 존재한다.
(W2) 임의의 정점 $v \in V(G)$에 대해 $\{t \in V(T) : v \in W_t \}$는 $T$의 연결된 부분그래프를 이룬다.

이를 만족하는 $(T,W)$를 $G$의 tree decomposition이라 부른다.

2.2 treewidth

tree decomposition $(T,W)$의 width는 $\max_{t \in V(T)} (|W_t| - 1)$ 로 정의한다.

그래프 $G$의 treewidth는 가능한 모든 tree decomposition 중 width의 최소값이다.

treewidth가 작을수록 그래프가 트리와 “가까운” 구조를 가진다고 볼 수 있다. 특히 tree의 treewidth는 1이다.

3. $c(G) \le tw(G) + 1$

Proof

아이디어는 tree decomposition $(T,W)$를 하나 고정하고, 경찰이 트리 $T$ 위를 따라 이동하면서 항상 하나의 bag을 지키는 전략을 사용하는 것이다.

루트 선택
트리 $T$의 임의의 정점 $r$을 루트로 잡는다.

불변량 설정
게임의 특정 시점마다 다음 조건을 유지하는 전략을 생각한다.

경찰의 정점 집합 $X$는 어떤 bag $W_t$ 전체를 포함한다. treewidth가 $k$이므로 모든 bag의 크기가 $

W_t

\le k+1$이고, $k+1$명의 경찰이면 이를 전부 점유할 수 있다.

도둑은 $T$에서 $t$를 제거했을 때의 어떤 한 컴포넌트에 대응하는 부분그래프 안에 갇혀 있다. 즉, $T - t$의 한 컴포넌트 $C$에 대해 도둑은 $\bigcup_{u \in V(C)} W_u$ 안에 위치하며, 현재 bag $W_t$를 통과하지 않고는 다른 컴포넌트로 이동할 수 없다.

트리 위의 전진 $t$의 자식 $t’$의 서브트리 안에 도둑이 존재한다고 하자. $W_{t’}$쪽으로 트리 상에서 한 단계씩 이동한다.
- $W_t \cap W_{t’}$에 있는 경찰은 유지시킨 후 나머지 경찰은 떠난다.
- 이후 경찰은 $W_{t’} \setminus W_t$에 도착한다.
- (W2)에 의해 도둑은 $t’$의 서브트리에서 벗어나지 못한다.
도둑 포획
트리 $T$는 유한하므로, 도둑이 있는 방향으로 계속 내려가다 보면 결국 leaf의 bag에 도달한다. 이 시점에서 도둑이 존재할 수 있는 영역은 더 분할될 수 없고, 경찰이 해당 bag 전체를 점유하고 있으므로, 일정 라운드가 지나면 도둑의 위치 $R_i$가 $X_i$와 일치하는 순간이 반드시 존재한다. 이때 경찰이 승리한다.

4. bramble: treewidth에 대한 하계와 장애물

treewidth의 반대편에는 bramble이라는 조합론적 구조가 존재하며, 이는 treewidth와 cop number에 대한 하계를 제공하는 장애물로 작동한다.

4.1 Bramble과 order의 정의

그래프 $G$에서 두 부분집합 $X,Y \subseteq V(G)$에 대해 다음 중 하나가 성립하면 $X$와 $Y$가 touch한다고 말한다.

$X \cap Y \neq \emptyset$, 또는
$X$의 어떤 정점이 $Y$의 어떤 정점과 인접하다.

정의 (bramble).
그래프 $G$의 bramble $\mathcal{B}$는 다음을 만족하는 정점집합들의 모임이다.

임의의 $B \in \mathcal{B}$에 대해, 유도 부분그래프 $G[B]$는 연결된 부분그래프이다.

임의의 서로 다른 $B,B’ \in \mathcal{B}$에 대해 $B$와 $B’$는 서로 touch한다. 즉, bramble은 서로 “떨어뜨려 분리할 수 없는” 연결 부분집합들의 가족이다.

Bramble $\mathscr{B}$의 cover는 $\mathcal{B}$의 모든 원소와 동시에 만나는 정점 집합이다.

Bramble의 order는 cover의 최소 크기이다.

4.2 Bramble에 의한 treewidth의 하계

명제.
그래프 $G$가 차수 $> k$인 bramble $\mathcal{B}$를 포함한다고 하자.
그러면 $tw(G) \ge k$이다.

증명 스케치

$ord(\mathcal{B}) > k$라고 가정하자. 모순을 위해 $tw(G) < k$라고 가정한다. 그러면 width가 $< k$인 tree decomposition $(T,W)$가 존재한다.

bag 크기의 상계
width가 $< k$이므로 모든 $t \in V(T)$에 대해서 $|W_t| \le k$이다.
bramble의 order와 bag의 한계
$ord(\mathcal{B}) > k$이므로, 크기가 $\le k$인 정점집합은 bramble의 모든 원소를 동시에 만날 수 없다.
특히 모든 $t \in V(T)$에 대해 $B_t \cap W_t = \emptyset$인 $B_t \in \mathcal{B}$가 존재한다. 즉, 어느 bag도 bramble 전체를 덮는 cover가 될 수 없다.
tree를 통한 분해와 방향 부여
트리 $T$의 간선 $e = uv$를 하나 고정한다. 이 간선을 제거하면 $T$는 두 컴포넌트 $C_u, C_v$로 나뉘고, $U := \bigcup_{t \in V(C_u)} W_t$, $V := \bigcup_{t \in V(C_v)} W_t$ 로 정의한다.

bramble의 각 원소 $B \in \mathcal{B}$는 연결되어 있고, 서로 touch하는 구조를 가지므로, $B$가 주로 포함되는 쪽(예를 들어 $U$ 쪽 또는 $V$ 쪽)을 기준으로 간선 $e$에 방향을 부여할 수 있다. 적절히 정의하면, 각 간선에 대해 하나의 방향을 선택할 수 있다.

트리는 유한하므로, 이렇게 방향을 부여하면 항상 진입 간선만 있고 이탈 간선은 없는 정점, 즉 싱크(sink) 정점 $t^{*}$가 존재한다.
싱크 bag이 만드는 hitting set
싱크 정점 $t’$에 대응하는 bag $W_{t’}$를 보자. 간선 방향의 정의에 의해 $\mathcal{B}$의 모든 원소 $P$에 대해 $W_{t’} \cap P \neq \emptyset$임을 알 수 있다. 직관적으로, 싱크 방향성 때문에 bramble의 어떤 원소도 $W_{t’}$와 완전히 떨어져 있을 수 없으며, 그렇지 않다면 그 원소가 있는 방향으로 나가는 간선의 방향이 싱크 속성과 모순된다. 따라서 $W_{t’}$는 bramble $\mathcal{B}$의 hitting set이 된다.
모순
그런데 $|W_{t’}| \le k$ 이므로, $ord(\mathcal{B}) > k$라는 가정과 모순이다.
따라서 width $< k$인 tree decomposition은 존재할 수 없고, $tw(G) \ge k$가 되어야 한다.

결과적으로, order $> k$인 bramble이 존재하면 treewidth는 적어도 $k$라는 하계를 갖는다.

5. 결론: $k+1$명의 경찰의 필요·충분성

앞선 절들을 종합하면, treewidth, bramble, cop number 사이에 다음 관계가 성립한다.

상계 (3절)
$tw(G) = k \Rightarrow c(G) \le k+1$

즉 treewidth가 $k$이면 $k+1$명의 경찰에게 도둑을 잡는 승리 전략이 존재한다.
하계 및 이중성 (4절 및 Seymour–Thomas 이중성 정리)
Seymour–Thomas의 min–max 이중성에 따르면, $tw(G) = k \Longleftrightarrow \exists \text{ bramble } \mathcal{B} \text{ with } ord(\mathcal{B}) = k+1$

즉, treewidth가 $k$인 그래프에는 order가 $k+1$인 bramble이 존재한다.

bramble의 order가 $k+1$이라는 것은, bramble의 모든 원소를 동시에 만나는 정점집합의 최소 크기가 $k+1$이라는 뜻이다. $k$명의 경찰은 어떤 시점에서도 최대 $k$개의 정점만 점유할 수 있으므로, 그 순간의 경찰 집합은 bramble의 hitting set이 될 수 없다. 항상 어떤 bramble 원소 $B \in \mathcal{B}$는 경찰이 점유하지 않은 정점들로만 이루어져 있다.

1절에서 정의한 게임에서 도둑은 경찰이 점유한 정점을 피해서 무한한 속도로 이동할 수 있으므로, 게임 내내 “경찰이 점유하지 않은 bramble 원소들” 사이를 이동하면서 경찰을 피할 수 있다. bramble 원소들이 서로 touch하므로, 도둑은 경찰이 점유한 정점을 통과하지 않고도 한 bramble 원소에서 다른 bramble 원소로 이동 가능하다. 따라서 $c(G) \ge k+1.$
필요·충분성 종합
treewidth $k$에 대해 $c(G) \le k+1 \text{(3절의 상계)}, c(G) \ge k+1 \text{(4절의 하계)}$ 가 동시에 성립하므로 $c(G) = k+1$ 이다.

요약하면, treewidth가 $k$인 그래프에서는 정확히 $k+1$명의 경찰이 필요하며, 이 수는 충분조건이자 필요조건이다.