Novos Algoritmos e Limites Inferiores para Torneios de Streaming

Estudamos problemas fundamentais de grafos direcionados (digrafos) no modelo de streaming. Uma investigação inicial de Chakrabarti, Ghosh, McGregor e Vorotnikova SODA'20 sobre digrafos de streaming mostrou que, embora a maioria desses problemas seja provadamente difícil em geral, alguns deles se tornam tratáveis quando restritos à classe bem estudada dos grafos de torneio, onde cada par de nós compartilha exatamente uma aresta direcionada. Assim, focamos nos torneios e melhoramos o estado da arte para múltiplos problemas em termos de limites superiores e inferiores. Nosso limite superior primário é um algoritmo determinístico de passagem única semi-streaming (usando O(n) espaço para grafos com n nós, onde O(.) oculta fatores polilog(n)) para decompor um torneio em componentes fortemente conectados (SCC). Ele melhora o algoritmo previamente conhecido por Baweja, Jia e Woodruff ITCS'22 em termos de espaço e passagens: para p=1, eles utilizaram (p+1) passagens e O(n^(1+1/p)) espaço. Além disso, estendemos nosso algoritmo para digrafos que estão próximos de torneios e estabelecemos limites rígidos demonstrando que a complexidade do problema cresce suavemente com a "distância" dos torneios. Aplicando nossa estrutura, obtemos algoritmos de torneio melhorados para alcançabilidade s, t, conectividade forte, caminhos e ciclos Hamiltonianos, e conjunto de arcos de feedback. Por outro lado, provamos os primeiros limites inferiores de espaço (n²) para esta classe, exibindo que alguns problemas bem estudados -- como conjunto de arcos de feedback (exato) em torneios (FAST) e distância s, t -- continuam difíceis aqui. Obtemos um limite inferior generalizado nos trade-offs de espaço-aproximação para FAST: qualquer algoritmo de aproximação (1)-passagem requer (n/) espaço. Como um todo, nossa coleção de resultados contribui significativamente para a literatura crescente sobre digrafos de streaming.