Encontre caminhos mais curtos no gráfico de complemento

Estou procurando um algoritmo que receba como entrada um vértice e encontre os caminhos mais curtos de para todos os vértices no gráfico do complemento (não direcionado). O algoritmo deve ser executado no tempo , onde é o número de arestas no gráfico original (não no gráfico do complemento).$s$$s$$O(V+E)$$E$

Se for um gráfico, o gráfico de complemento é definido como o seguinte gráfico: é uma aresta no gráfico de complemento, se e somente se não for uma aresta no gráfico original. Em outras palavras, excluímos todas as arestas existentes e adicionamos todas as arestas que estavam faltando no gráfico original.$G$$e$

Então, primeiro, é claro, pensei em "construir" o gráfico do complemento (substituindo os vértices na lista de adjacências por aqueles que não aparecem lá), depois executando o BFS na nova lista, mas é claro que isso significaria que o tempo de execução seria baseado nas arestas do gráfico do complemento, não no original.

Também notei, é claro, que, depois de executar o BFS no gráfico original, qualquer vértice que tenha uma distância de maior que 1 (no gráfico original) deve se tornar 1 no gráfico de complemento (porque se eles não eram vizinhos no gráfico original, são vizinhos no gráfico de complemento). Mas não consegui fazer com que o algoritmo continuasse de acordo com algumas regras específicas sobre quando a distância deveria ser atualizada e o quê. Alguma sugestão?$s$

Pessoalmente, não vejo por que isso é deixado sem resposta .

Encontrar algo no gráfico de complemento e encontrar a mesma coisa no gráfico é essencialmente ter a mesma complexidade de tempo (até fator constante).

Desde a troca entre borda $(u,v)$ e sem borda $(u,v)$ é apenas $O(1)$tempo de operação. Não precisamos transformar ou converter nada, apenas negar todas as saídas da consulta .