Problema de espectro de gráfico reverso?

25

Geralmente, constrói-se um gráfico e, em seguida, faz-se perguntas sobre a decomposição do autovalor da matriz de adjacência (ou algum parente próximo como o Laplaciano ) (também chamado de espectro de um gráfico ).

Mas e o problema inverso? Dados valores próprios, é possível (eficientemente) encontrar um gráfico que possua esse espectro?n

Eu suspeito que, em geral, isso é difícil de fazer (e pode ser equivalente ao IG), mas e se você relaxar um pouco as condições? E se você criar condições para que não haja multiplicidade de autovalores? Que tal permitir gráficos com espectros "próximos" por alguma métrica de distância?

Quaisquer referências ou idéias serão bem-vindas.

EDIT :

Como Suresh ressalta, se você permitir gráficos ponderados não direcionados com auto-loops, esse problema se tornará bastante trivial. Eu esperava obter respostas sobre o conjunto de gráficos simples não direcionados e não ponderados, mas também ficaria feliz com os gráficos direcionados não ponderados.

ds.algorithms graph-theory graph-algorithms spectral-graph-theory user834
fonte
2
Eu acho que você pode precisar modificar a pergunta para 'gráficos não direcionados não ponderados, sem auto-loops' ou algo assim? Posso imaginar a construção de uma matriz diagonal com os valores próprios necessários e a declaração de um gráfico desconectado com selfloops ponderados?
Suresh Venkat
6
A pergunta ainda mais simples (não sei a resposta) é como construir gráficos conectados simples, cujos poucos autovalores são dados
Yaroslav Bulatov
5
Uma maneira alternativa de declarar a questão (a versão com gráficos simples não-direcionados) é: dados n números reais (em algum formato), decida se existe uma matriz n × n simétrica 0/1 com diagonais zero, de modo que seus n valores próprios sejam os determinados números.
Tsuyoshi Ito
1
@Yaroslav: Não tenho certeza, mas esse problema me parece mais difícil do que o caso em que todos os n autovalores são dados.
Tsuyoshi Ito 12/12
8
Observação minúscula: se não temos restrições quanto aos valores próprios, o problema é realmente difícil (mesmo que não inclua a parte algorítmica), pois isso implica a (não) existência no gráfico Moore de 57 anos , cujos valores próprios são todos conhecidos.
Hsien-Chih Chang,

Respostas:

10

Cvetcovic et all na Seção 3.3 do "Os resultados recentes na teoria dos espectros gráfico" vai sobre algoritmos para a construção de gráficos dada espectro em alguns casos especiais

Yaroslav Bulatov
fonte
10

Mesmo perguntar se existe um gráfico com um determinado espectro é uma pergunta difícil. Isso é testemunhado pelo problema aberto de determinar se existe um gráfico de perímetro 5 de diâmetro 2 e ordem 3250 cujo espectro (se existir) é conhecido.

Jernej
fonte
3

Um outro obstáculo para definir sua pergunta é que são gráficos isoespectrais (mesmos valores próprios), mas não isomórficos. Então, dada uma lista de autovalores nesse caso, qual gráfico você deseja? Talvez você queira apenas que um algoritmo retorne um elemento aleatório do conjunto desses gráficos não isomórficos?

dabacon
fonte
Eu estava pensando em algo ao longo das linhas de amostragem a partir do espaço de gráficos isoespectrais, mas parece que estamos descendo rapidamente para um problema equivalente de IG (portanto, meu comentário acima). Por uma questão de simplicidade, poderíamos restringir a todos os autovalores distintos (que, se a IIC garantir um gráfico único), mas estou apenas tentando ver o que é conhecido ou o que existe por aí.
user834
5
Eu não acho que autovalores distintos Garante reconstructibility, aqui estão alguns espectros de gráficos isospectral mais de 7 nós yaroslavvb.com/upload/save/cstheory-isospectral.png
Yaroslav Bulatov
3
Eu gosto da formulação de elementos aleatórios. Eu estaria interessado em saber se é equivalente a IG. Uma das razões pelas quais estou interessado na formulação de elementos aleatórios é a questão levantada em meu artigo com Arora e Steurer em jogos únicos, sobre se gráficos com determinado espectro podem ser expansores para pequenos conjuntos. Intuitivamente, pode-se esperar que um gráfico aleatório com esse espectro seja o melhor expansor possível para todos os tamanhos definidos, e, portanto, a percepção dos espectros reversos pode ser útil.
precisa
@Yaroslav: Obrigado por esse link e obrigado por me corrigir!
user834
1
@ user834: Re: seu comentário sobre um problema equivalente ao IG. Observe que a determinação do isomorfismo de gráficos com multiplicidade limitada de autovalores (em particular, gráficos sem múltiplos autovalores) pode ser feita em tempo polinomial.
Joshua Grochow