Discutimos uma recente publicação (prêmio de melhor papel) no Simpósio ACM-SIAM sobre algoritmos discretos (SODA24), que fornece um algoritmo determinístico de tempo de execução quase linear para o problema de otimização elementary de encontrar um corte mínimo nos gráficos ponderados.
UM gráfico é uma estrutura de dados onipresente usada na ciência da computação que consiste em nós (ou vértices) e bordas entre pares de nós para capturar objetos e suas relações. O problema mínimo de corte (Frequentemente chamado de “Min-Minimize”) é uma questão estrutural básica sobre a conectividade de um gráfico que pergunta: Qual é a maneira mais barata de desconectar uma rede? Mais formalmente, dado um gráfico de entrada onde as bordas têm Sem orientação (ou seja, o gráfico é não direcionado) e estão associados a pesos positivos, quantificando a importância das bordas (por exemplo, capacidade de uma estrada ou força de um relacionamento, nível de similaridade entre os pontos finais, and so forth.), um corte é uma partição dos nós em dois lados. O tamanho de um corte é o peso complete das bordas que conectam nós em lados diferentes do corte, e o problema do minúsculo é encontrar um corte do tamanho mínimo.
Resolvá -lo com eficiência tem sido um dos problemas mais fundamentais na teoria dos gráficos algorítmicos. Além disso, o MIN-CUT possui diversas aplicações na prática, como restauração de imagens, estéreo e segmentação na visão computacional e análise de resiliência de rede (como para estradas ou grades de energia). Também é geralmente muito útil quando os dados do gráfico subjacente são muito grandes e precisam ser particionados em componentes menores a serem processados de maneira dividida e conquistada.
Na teoria do design do algoritmo, o complexidade assintótica Para qualquer problema que exija a leitura de toda a entrada (o que é o caso do MINCUT) é pelo menos linear no tamanho da entrada (pois esse é o tempo necessário para ler a entrada). UM tempo quase linear O algoritmo atinge essencialmente esse limite inferior e, portanto, é visto canonicamente como o resultado ideally suited que se pode alcançar. Para o problema de minúsculo, os algoritmos de tempo quase lineares existentes são randomizados (que podem gerar uma resposta incorreta com alguma probabilidade) ou apenas funcionam para o caso especial quando o gráfico é simples (que não pode modelar muitas aplicações do mundo actual), portanto, sua complexidade ideally suited continua sendo um problema aberto.
Em “Tempo quase linear determinístico corte mínimo em gráficos pesados”, Que co-varia o prêmio de melhor artigo no Simpósio ACM-Siam sobre algoritmos discretos (Soda2024), projetamos o primeiro algoritmo quase linear para o problema do minúsculo que é determinístico (ou seja, sempre encontra a resposta correta) e que também funciona para gráficos gerais, resolvendo assim a complexidade ideally suited para o problema do minúsculo.
Insights técnicos
Nosso resultado é o culminar de uma longa linha de pesquisa, e os avanços algorítmicos sobre esse problema (incluindo o nosso) são geralmente motivados por descobertas estruturais da conectividade gráfica. Em specific, um resultado seminal por Karger em 1996 Deu um algoritmo randomizado quase linear que encontra um minúsculo com alta probabilidade, e uma visão crítica desse trabalho foi a existência de um gráfico muito menor que preserva amplamente o tamanho de todos os cortes. Isso é útil, pois é possível executar um algoritmo mais lento com o gráfico menor como entrada e o tempo de execução mais lento (em termos do tamanho do gráfico menor) ainda pode ser quase linear no tamanho do authentic (maior) gráfico. De fato, muitas das descobertas estruturais sobre o problema do minúsculo estão nessa direção, e a idéia de alto nível de reduzir o tamanho do problema, preservando as estruturas de interesse, tem sido amplamente impactante no design do algoritmo.
Esparsificação de gráficos de preservação de corte
Começamos discutindo o perception estrutural usado por Karger com mais detalhes. Começando com um gráfico G com n nós, a esparsificação de preservação de corte por Benczúr e Karger estabeleceu a existência de um esparso ponderado gráfico G‘ no mesmo conjunto de nós com um número menor de bordas de modo que com alta probabilidade, cada corte Stamanho em G‘ é aproximadamente o mesmo que seu tamanho em G. Essa idéia é ilustrada abaixo, onde o gráfico authentic consiste em dois gráficos completos conectados por uma única borda (ou seja, o gráfico de halteres), e o gráfico sparsificado tem menos, mas maior peso, bordas, enquanto todos os tamanhos de corte são preservados aproximadamente.
Ilustração da escarsificação do gráfico de preservação de corte.
Para construir algoritmicamente um gráfico mais escasso, Benczúr e Karger usaram a abordagem de bordas de amostragem de forma independente, onde cada borda em G está incluído em G‘ com alguma probabilidade e seu peso em G‘ é escalado pelo recíproco da probabilidade de amostragem (por exemplo, uma borda do peso authentic 1 em G teria um peso de 10 em G‘ Se estiver incluído com um 10% likelihood). Acontece que, com alta probabilidade, esse método notavelmente simples (e quase linear) pode construir com êxito uma escarsificação gráfica de preservação de corte.
A escarsificação do gráfico de preservação de corte, juntamente com várias outras idéias algorítmicas criativas, produziu o resultado de Karger. No entanto, o algoritmo de Karger é um Algoritmo de Monte Carloou seja, a saída pode estar incorreta com (pequena) probabilidade, e não há uma maneira conhecida de saber se a saída está correta além de compará-la com um minimize de min de um min. Desde então, os pesquisadores estão na busca de resolver a questão em aberto de um algoritmo determinístico de tempo quase linear. Em specific, a construção do gráfico de preservação de corte é o único componente no algoritmo de Karger que é randomizado, e uma receita aparente é encontrar uma construção determinística (também conhecida como desanimação) da escarsificação em tempo quase linear.
Em 2015, Kawarabayashi e Thorup alcançou um marco importante com um algoritmo de tempo quase linear tão determinístico para gráficos simples, ou seja, gráficos que têm no máximo uma vantagem entre cada par de nós e todos os pesos de borda iguais a 1. A observação chave nesse trabalho é uma conexão entre o MIN-CUT e outra estrutura gráfica importante conhecida como corte de baixa condutância (explicado abaixo). Essa conexão também acabou sendo crítica nos esforços posteriores para desativar o algoritmo de Karger nos gráficos de pesos gerais da borda, que eventualmente culminaram em nosso resultado.
Alinhamento de corte min-corte e baixa condutância
O condutância de um corte S é definido como a proporção do tamanho de corte de S sobre o quantity de S (assumindo S é o lado de quantity menor do corte e não está vazio), onde o quantity de S é a soma do grau dos nós em S. Um corte S de baixa condutância captura intuitivamente um gargalo em uma rede, pois há apenas um pequeno número de arestas (em relação ao seu quantity) conectando S para o restante do gráfico. A condutância de um gráfico é definida como a minim condutância de qualquer corte no gráfico e um gráfico de grande condutância (também conhecido Gráfico de expansão) é considerado bem conectado, pois não há gargalo dentro.
O corte representado pela linha pontilhada vermelha tem tamanho 2 e o lado menor (o fundo) possui o quantity 24, portanto sua condutância é 1/12, que também é a condutância do gráfico.
Kawayabarashi e Thorup fizeram a observação de que qualquer min-corte não trivial (ou seja, ambos os lados tem pelo menos dois nós) deve ter baixa condutância em um gráfico simples, onde o grau de nó min é grande. Após essa observação, se alguém puder particionar o gráfico em clusters bem conectados, o particionamento deve ser consistente com todos os mínimos não triviais, no sentido de que cada cluster deve estar inteiramente em um lado de cada corte. Pode-se contratar cada cluster em um único nó e trabalhar no gráfico menor, onde todos os minúsculos não triviais do gráfico authentic estão intactos.
No entanto, para gráficos ponderados, a mesma observação não é mais segurada, e a mesma partição usada no caso de gráfico simples pode não ser exatamente consistente com os minúsculos não triviais. Apesar disso, Li 2021 observaram que tal partição ainda é aproximadamente consistente com os minúsculos não triviais, como ilustrado na figura abaixo. Em specific, para um min-corte não trivial Sexiste um corte S‘ Isso não é muito diferente de S tais que S‘ é consistente com os clusters. Li observou ainda que essa propriedade do particionamento pode ser explorada para despersar eficientemente a construção da escarsificação de gráficos de preservação de corte.
Uma partição do gráfico que é aproximadamente consistente com os cortes de quase minúmio.
Em nosso novo resultado, inventamos um algoritmo para construir esse particionamento adaptado ao nosso caso de uso de encontrar o Min-Minimize. Comparado ao método mais genérico de prateleira usado por Li no trabalho anterior, nossa construção personalizada é muito mais precisa, de modo que o Min-Minimize authentic S e seu corte correspondente consistente de cluster S‘ (na figura acima) têm garantia de ter tamanhos de corte mais semelhantes. Além disso, nosso algoritmo é mais rápido que os métodos prontos para uso, que surgem melhorando as técnicas anteriores de agrupamento desenvolvidas apenas para gráficos simples (por Henzinger, Rao e Wang em 2017) para trabalhar de maneira mais ampla em gráficos ponderados. As garantias mais fortes de precisão e tempo de execução alcançadas pela nova construção, em última análise, levam ao nosso algoritmo determinístico de tempo quase linear para o problema do minúsculo.
Agradecimentos
Somos gratos aos nossos co-autores Monika Henzinger, Jason Li e Satish Rao. Também gostaríamos de agradecer especial a John Guilyard por criar a animação usada neste submit.