Classes gráficas para as quais o diâmetro pode ser calculado em tempo linear

11

Recordar o diâmetro de um gráfico que é o comprimento de um caminho mais longo que mais curto em . Dado um gráfico, um algoritmo óbvio para calcular resolve o problema de caminho mais curto de todos os pares (APSP) e retorna o comprimento do caminho mais longo encontrado.G diam ( G )GGdiam(G)

Sabe-se que o problema do APSP pode ser resolvido no tempo ideal para várias classes de gráficos. Para gráficos gerais, existe uma abordagem teórica de gráfico algébrico em execução no tempo , em que é o limite para a multiplicação de matrizes. No entanto, calcular o diâmetro aparentemente não está vinculado criticamente ao APSP, como mostra Yuster .O ( M ( n ) log n ) M ( n )O(n2)O(M(n)logn)M(n)

Existem algumas classes de gráficos não triviais conhecidas pelas quais o diâmetro pode ser calculado ainda mais rápido, digamos em tempo linear?

Estou especialmente interessado em gráficos de acordes e em quaisquer subclasses de gráficos de acordes, como gráficos de blocos. Por exemplo, acho que o diâmetro de um gráfico acorde pode ser calculado em tempo, se for representável exclusivamente como uma árvore de clique. Esse gráfico também é conhecido como ur-chordal .O ( n + m ) GGO(n+m)G

Juho
fonte
Para o cálculo do diâmetro, uma vez fornecida a árvore de clique, os gráficos de acordes se comportam (quase) da mesma forma que as árvores. Da mesma forma, em um gráfico de intervalo, um par dominante (que existe em qualquer gráfico sem AT) decide necessariamente o diâmetro.
Yixin Cao
@YixinCao Mas, em geral, o número de árvores de clique distintas que um gráfico de acordes pode ter é exponencial no número de vértices. Além disso, não acho que o diâmetro seja o mesmo em todas as camarilhas. Eu acho que isso é um problema, mas em um gráfico ur-cordal o diâmetro da árvore de camarilha não é ambíguo. Você tinha outra coisa em mente?
Juho
Não estou dizendo que o diâmetro do gráfico acorde seja o mesmo da sua árvore de clique. (Uma estrela de vértices pode ter uma árvore de clique que é um caminho de nós.) O que eu quis dizer é que o diâmetro do gráfico deve estar entre algum par de folhas (qualquer vértice simples nele) na árvore de clique. kk+1k
Yixin Cao
@YixinCao OK, agora eu entendo melhor. Mesmo assim, um algoritmo (rápido) ainda não é óbvio para mim. Se você tiver mais detalhes ou referências, sinta-se à vontade!
Juho

Respostas:

9

A excentricidade de um vértice é o comprimento de um caminho mais curto e mais longo, começando em . O diâmetro é a excentricidade máxima em todos os vértices. Qualquer BFS de um vértice estabelecerá sua excentricidade. Uma idéia chave para encontrar um diâmetro eficiente é, portanto, pré-processar o gráfico para encontrar um pequeno conjunto de vértices, pelo menos um dos quais atinge a excentricidade máxima.vv

Executando uma pesquisa lexicográfica de largura em primeiro lugar , o vértice final geralmente possui alta excentricidade. Em particular, é garantido que tenha excentricidade no máximo um a menos do que o diâmetro para gráficos de acordes. Para algumas subclasses de gráficos de acordes, como gráficos de intervalo , é garantido que tenha uma excentricidade máxima. Isso também vale para algumas classes não cordais, como gráficos livres de .{AT,claw}

LBFS e BFS são lineares no tamanho do gráfico, mas é claro que se (como ), o tempo de execução não será . Sua discussão implica que você provavelmente realmente deseja um algoritmo linear vez de .m=Ω(n2)Kno(n2)O(m+n)o(n2)

Portanto, para algumas subclasses de gráficos cordais, um algoritmo linear é executar o LBFS, pegar o vértice final e executar o BFS começando nesse vértice. Para gráficos de corda, isso determinará o diâmetro com um erro de no máximo 1. Os gráficos para os quais isso é exato parecem ser aqueles em que as potências pares são cordais. Estes são precisamente aqueles gráficos de acordes que não contêm sol nascente ou subgráfico que preserva distâncias.(rising sunK2)

gráfico do sol nascente
(fonte: graphclasses.org )

  • Feodor F. Dragan, Falk Nicolai e Andreas Brandstädt, pedidos do LexBFS e poderes dos gráficos , WG 1996, LNCS 1197, 166–180. doi: 10.1007 / 3-540-62559-3_15

Não sei se isso pode ser estendido para calcular com precisão o diâmetro de todos os gráficos de acordes. A pesquisa de Corneil parece indicar que isso ainda estava aberto em 2004. Também não sei se foi feita uma análise para estender a pesquisa de um vértice para um pequeno número constante ou vértices iniciais; isso pode ser interessante para explorar.logn

András Salamon
fonte
O(n+m)o(n2)