Resolvendo a Complexidade de Passes de Correspondências Aproximadas em Fluxos de Grafo Dinâmico

Um algoritmo semi-streaming em fluxos de grafos dinâmicos processa qualquer grafo de n vértices fazendo uma ou múltiplas passagens sobre um fluxo de inserções e deleções nas arestas do grafo e utilizando O (n polylog (n)) espaço. Algoritmos semi-streaming para fluxos dinâmicos foram obtidos pela primeira vez no trabalho seminal de Ahn, Guha e McGregor em 2012, juntamente com a introdução da técnica de esboço de grafo, que continua a ser a maneira de fato de projetar algoritmos neste modelo e uma técnica bastante popular para projetar algoritmos de grafos em geral. Nós resolvemos a complexidade de passes da aproximação de correspondências máximas em fluxos dinâmicos via algoritmos semi-streaming, melhorando o estado da arte em ambos os limites superior e inferior. Apresentamos um algoritmo semi-streaming baseado em esboços aleatórios para aproximação de O (1) de correspondência máxima em fluxos dinâmicos usando O () passes. A razão de aproximação deste algoritmo pode ser melhorada para (1+) para qualquer fixo > 0, mesmo em grafos ponderados utilizando técnicas padrão. Isso melhora exponencialmente vários algoritmos de passes O (n) desenvolvidos para este problema desde a introdução do modelo de streaming de grafos dinâmicos. Além disso, provamos que qualquer algoritmo semi-streaming (não apenas baseado em esboços) para aproximação de O (1) de correspondência máxima em fluxos dinâmicos requer () passes. Isso apresenta o primeiro limite inferior de múltiplos passes para este problema, que já é também ótimo, resolvendo uma questão aberta de longa data nesta área.