Patrolling cop vs omniscient robber

Este artigo inicia um estudo sistemático de uma variante do jogo "Polícia e Ladrão" em que um policial segue uma patrulha fixa pré-determinada contra um ladrão onisciente, determinando o raio de captura mínimo necessário para garantir a captura em diversas classes de grafos, como árvores, grades e grafos cordais.

O essencial

Imagine um jogo de "esconde-esconde" muito especial, mas com uma regra que muda tudo: o policial não pode pensar à medida que joga. Ele já decidiu, antes do jogo começar, exatamente por onde vai andar. É como se ele estivesse seguindo um roteiro de TV gravado.

Por outro lado, o ladrão é um gênio da computação (ou um "omnisciente"). Ele roubou esse roteiro! Ele sabe exatamente onde o policial estará a cada segundo, para sempre. O objetivo do ladrão é usar essa vantagem para nunca ser pego.

O grande mistério que os autores deste artigo tentam resolver é: Qual é o tamanho do "raio de visão" que o policial precisa ter para garantir que pegue o ladrão, mesmo sabendo que o ladrão conhece todo o seu plano?

Vamos traduzir os conceitos técnicos para analogias do dia a dia:

1. O Cenário: O Policial Cego vs. O Ladrão Onisciente

• O Policial (Patrulha): Ele tem um mapa fixo. Ele não pode mudar de direção se vir o ladrão. Ele só sabe que vai passar pelo ponto A, depois pelo B, depois pelo C.
• O Ladrão: Ele vê o futuro. Ele sabe que o policial vai passar pelo ponto B daqui a 5 minutos. Então, ele se esconde no ponto Z, que fica longe do B, mas perto de onde o policial vai passar depois.
• O Raio de Captura ($\rho$): O policial não precisa pisar exatamente no pé do ladrão para prendê-lo. Se ele estiver a uma certa distância (digamos, 2 quadras de distância), ele consegue ver o ladrão e prendê-lo. O artigo pergunta: "Qual é o tamanho mínimo desse raio de visão para que o policial sempre ganhe?"

2. As Regiões do Jogo (Os Tipos de Mapas)

Os autores testaram esse jogo em diferentes "terrenos" (grafos matemáticos) para ver como o tamanho do raio de visão muda.

A. Árvores (Como um Galho de Árvore)

Imagine uma árvore com um tronco principal e vários galhos saindo.

• A Descoberta: Se a árvore tiver um "nó" (um ponto onde saem 3 galhos longos), o ladrão pode ficar pulando de um galho para o outro, sempre ficando um passo à frente do policial.
• A Analogia: Pense em um policial patrulhando um parque com três caminhos longos. Se os caminhos forem muito longos, o ladrão pode ficar no final de um caminho. Quando o policial se aproxima, o ladrão corre para o outro caminho.
• O Resultado: O tamanho do raio de visão necessário depende de quão "longos" são esses galhos. Se os galhos forem curtos, o policial precisa de pouco raio. Se forem longos, ele precisa de um raio enorme (ou seja, precisa ver de longe).

B. Grades (Como um Tabuleiro de Xadrez ou Cidade em Quadrícula)

Imagine uma cidade com ruas e avenidas formando quadrados perfeitos.

• O Desafio: Aqui, o ladrão tem mais espaço para correr em todas as direções.
• A Descoberta: O artigo mostra que, em cidades grandes, o policial precisa de um raio de visão que cubra quase metade da largura da cidade para garantir a captura. É como se o policial precisasse ter "visão de raio-X" para cobrir todas as esquinas ao mesmo tempo.

C. Grafos Cordais e "Caterpillars" (Lagartas)

• O que é uma "Caterpillar" (Lagarta)? Imagine um tronco de árvore com muitos galhos curtos saindo dele, parecendo as pernas de uma lagarta.
• A Grande Surpresa: Se o mapa for uma "lagarta", o policial não precisa de nenhum raio de visão extra (raio 0)! Ele só precisa andar pelo tronco principal.
• Por que? Porque em uma lagarta, todos os esconderijos estão tão perto do caminho principal que, se o policial passar pelo caminho, ele inevitavelmente vai ver o ladrão, não importa onde ele esteja. É como patrulhar um corredor estreito onde não há esconderijos escondidos atrás de portas.
• Grafos Intervalo: Para um tipo específico de mapa (grafos de intervalo), a regra é simples: ou é uma "lagarta" (raio 0) ou não é (raio 1). Se não for uma lagarta, o policial precisa apenas de um raio de visão muito pequeno (vizinho imediato) para vencer.

3. A Conclusão Principal

O artigo nos ensina que a estrutura do terreno é mais importante do que a velocidade ou a inteligência do ladrão.

• Se o terreno tem "pontos de decisão" complexos (como árvores com galhos longos ou cidades grandes), o policial precisa de uma visão de longo alcance (um raio grande) para compensar o fato de não poder mudar de rota.
• Se o terreno é simples e linear (como uma "lagarta"), a visão é irrelevante; o policial ganha apenas por estar no lugar certo na hora certa.

Resumo em uma frase

Este estudo é como um manual de estratégia para um policial que não pode improvisar: ele nos diz exatamente quão longe ele precisa conseguir ver para garantir a captura de um ladrão que conhece todos os seus passos, dependendo se o crime acontece em uma floresta, uma cidade ou um corredor simples.

Resumo técnico

Resumo Técnico: Patrolling Cop vs Omniscient Robber

Autores: Nina Chiarelli, Paul Dorbec, Miloš Stojaković e Andrej Taranenko.
Contexto: Teoria dos Grafos, Jogos de Perseguição e Evasão (Pursuit-Evasion Games).

1. O Problema

O artigo investiga uma variante do clássico jogo "Policial e Ladrão" (Cops and Robbers) em grafos finitos e não direcionados. Diferente do modelo clássico, onde ambos os jogadores têm informação perfeita e podem reagir dinamicamente aos movimentos um do outro, este modelo impõe restrições assimétricas de informação e estratégia:

• O Policial (Cop): Possui um caminho fixo de patrulha (walk) que é escolhido antes do jogo começar e não pode ser alterado durante o jogo. O policial não tem informação sobre a posição atual do ladrão.
• O Ladrão (Robber): É onisciente. Ele conhece toda a sequência de movimentos do policial (a patrulha) com antecedência e usa esse conhecimento para evitar a captura.
• Captura: Ocorre quando o ladrão está a uma distância $\rho$ (raio de captura) do policial. O objetivo é determinar o mínimo raio de captura $\tilde{\rho}(G)$ necessário para que o policial garanta a captura do ladrão em um grafo $G$ conectado, sob jogada ótima do ladrão.

Este modelo situa-se na interseção entre jogos de visibilidade limitada (onde o policial não vê o ladrão) e versões offline de problemas de perseguição, onde a estratégia é pré-determinada.

2. Metodologia e Ferramentas Teóricas

Os autores desenvolvem uma análise estrutural baseada em propriedades de grafos e homomorfismos:

• Retratos Fracos (Weak Retracts): Utilizam o conceito de retrato fraco e homomorfismo fraco para estabelecer limites inferiores. O Teorema 2.1 demonstra que se um subgrafo $H$ é um retrato fraco de $G$ e $\tilde{\rho}(H) > \rho$, então $\tilde{\rho}(G) > \rho$. Isso permite reduzir o problema de grafos complexos para subgrafos mais simples (como árvores ou ciclos).
• Estratégias de "Casa" (Houses): Para grafos com estruturas de "trios" (três ramos saindo de um nó central), definem "casas" (subconjuntos de vértices nas extremidades dos ramos) onde o ladrão pode se esconder. A análise foca na capacidade do policial de "ver" (cobrir com raio $\rho$) essas casas antes que o ladrão possa trocar de ramo.
• Projeções em Grades: Para grades (grids), utilizam projeções complexas ($\phi_{\uparrow}$ e $\phi_{\downarrow}$) para mapear o movimento do ladrão em uma árvore induzida, permitindo provar que o ladrão pode escapar se o raio for insuficiente.

3. Principais Resultados e Contribuições

Os autores determinam valores exatos ou limites para $\tilde{\rho}(G)$ em várias classes de grafos:

A. Árvores e Grafos Unicíclicos

• Árvores: O valor exato é dado por $\tilde{\rho}(T) = \max_{v \in V(T)} \lfloor \ell_3(v) / 2 \rfloor$, onde $\ell_3(v)$ é o tamanho do menor triodo (três ramos) com origem em $v$.
  • Interpretação: O policial precisa de um raio capaz de cobrir metade da distância do nó central até a folha mais próxima em um triodo, garantindo que o ladrão não possa trocar de ramo sem ser detectado.
• Grafos $T_{k,\ell}$ (Ciclo com três caminhos): Para grafos formados por um ciclo de comprimento $3k$com três caminhos de comprimento$\ell$anexados, o valor é$\max { \lceil \frac{\ell}{2} + \frac{k-2}{4} \rceil, \lceil \frac{3k-2}{2} \rceil }$.
• Cliques-Triodos: Para grafos com um núcleo de clique e três caminhos, $\tilde{\rho}(G) = \lceil \ell/2 \rceil$.

B. Grades (Grids)

• Para grades $P_n \square P_m$ (com $n \le m$), estabelecem limites:
  $$\min \left\{ \frac{n-3}{2}, \frac{2m+n-10}{8} \right\} \le \tilde{\rho}(P_n \square P_m) \le \frac{n}{2}$$
• Mostram que, embora um policial possa vencer em uma grade com raio $n-1$ no modelo clássico, a restrição de patrulha fixa exige um raio significativamente maior (aproximadamente $n/2$) para garantir a captura contra um ladrão onisciente.

C. Grafos Cordais (Chordal Graphs)

• Caterpillars (Gafanhotos): Um grafo $G$ tem $\tilde{\rho}(G) = 0$ se e somente se for um caterpillar (uma árvore onde todos os vértices estão a distância 1 de um caminho central). Neste caso, o policial pode capturar o ladrão sem precisar de raio de captura (apenas ocupando o vértice), desde que siga a espinha dorsal.
• Grafos de Intervalo:
  • Se o grafo é um caterpillar, $\tilde{\rho}(G) = 0$.
  • Caso contrário, $\tilde{\rho}(G) = 1$. Ou seja, um raio de captura de 1 é suficiente para qualquer grafo de intervalo que não seja um caterpillar.
• Conjectura Geral para Grafos Cordais: Os autores conjecturam que para um grafo cordal $G$, $\tilde{\rho}(G) \ge \rho$ se e somente se existir um retrato fraco que seja um triodo $T$ com $\ell_3(T) \ge 2\rho$ ou um clique-triodo com $\ell_3(G) \ge 2\rho - 1$.

4. Significado e Impacto

• Generalização de Modelos: O trabalho generaliza o problema de visibilidade zero (zero-visibility), forçando estratégias determinísticas em vez de probabilísticas. Isso preenche uma lacuna entre jogos com informação perfeita e jogos com informação parcial.
• Relação com "Watchman's Walk": O modelo conecta-se diretamente ao problema do "caminho do guarda" (watchman's walk), onde o objetivo é visitar ou ver todos os vértices. O resultado mostra que, contra um adversário onisciente, a simples cobertura de vértices não é suficiente; a sequência e o tempo de cobertura são críticos.
• Limites de Recursos: O estudo demonstra que a restrição de informação e a predefinição de estratégia podem aumentar drasticamente os recursos necessários (raio de captura) para vencer, mesmo em grafos que são "cop-win" no modelo clássico.
• Ferramentas Estruturais: O desenvolvimento de ferramentas como retratos fracos aplicados a jogos de perseguição oferece novos métodos para analisar jogos de informação limitada em outras classes de grafos.

Em resumo, o artigo estabelece uma teoria fundamental para jogos de perseguição onde o perseguidor tem uma estratégia fixa e o evasor tem informação completa, fornecendo soluções exatas para árvores e grafos de intervalo, e limites rigorosos para grades e grafos cordais.