Os gráficos com grande número de caminhos contêm cadeias menores menores?

8

Definição: Uma " cadeia " é um multi-gráfico obtido a partir de um caminho de comprimento k , duplicando todas as arestas.kk

Observe que o número de caminhos entre dois pontos finais de uma cadeia é 2 k .k2k.

Pergunta: Let ser um simples gráfico no n nós e deixe s e t seja dois nós de G . Suponha que o número de caminhos (simples) de s a t em G seja pelo menos n k . Então, é possível obter uma cadeia Ω ( k ) de G com ( s e t como pontos finais) por uma sequência de exclusão e contração de arestas?GstG.Gnk.Ω(k)Gst

Se a resposta for positiva, a segunda parte da pergunta é se existe um algoritmo eficiente para obter uma cadeia tão grande.

Eu ficaria igualmente feliz com cadeia k oukαpara qualquerα>0.kkαα>0.

Eu apreciaria qualquer resposta parcial ou qualquer intuição sobre se tal conjectura se sustentaria.

Eu tinha postado isso no excesso de matemática alguns dias atrás. Alguém sugeriu publicá-lo aqui também.

/mathpro/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor

Raghav Kulkarni
fonte
Pode valer a pena verificar o gráfico recursivo do diamante para ver se é um exemplo contrário. cstheory.stackexchange.com/questions/10169/...
Chandra Chekuri
kαΩ(k)
Ω(k)Ω(k)sO(k)s,tO(k)nkn=f(k)fé função exponencial).
Saeed
Um contra-exemplo é publicado no MathOverflow: mathoverflow.net/questions/161451/… Ainda sinto que a modificação "correta" da pergunta pode ser verdadeira, pelo menos para algumas classes de gráficos naturais, como gráficos planares.
Raghav Kulkarni
kk

Respostas:

2

ks,tk×ks,tO(k1/δ)δ>0é alguma constante. Assim, podemos calcular a decomposição em árvore do gráfico e verificar se essa cadeia existe ou não. Não sei se, com a programação dinâmica usual em gráficos de largura de árvore delimitada, é possível encontrar a cadeia. Além disso, se a largura da árvore não for limitada, seu algoritmo poderá encontrar a grade correspondente em tempo polinomial.

nk

Saeed
fonte
Então você está dizendo que a "maior cadeia obtida por deleção-contração" parece ser um parâmetro fixo tratável. Isso é interessante! Embora isso não conte nada sobre a existência de uma grande cadeia como conseqüência de ter um grande número de caminhos.
Raghav Kulkarni 03/04
@RaghavKulkarni, Sim, acho que sim, não tenho muita certeza, só depende disso, se for possível formular um problema como MSO_2 ou fornecer uma abordagem de programação dinâmica para casos com largura de árvore limitada, na verdade, seu problema parece estar na categoria de problemas bidimensionais.
Saeed #
K×K2kP