¿Los gráficos con un gran número de rutas contienen cadenas menores grandes?

8

Definición: Una " cadena " es un gráfico múltiple obtenido a partir de una ruta de longitud al duplicar cada borde.kk

Tenga en cuenta que el número de rutas entre dos puntos finales de una cadena esk2k.

Pregunta: Sea un gráfico simple en n nodos y sea y dos nodos de Suponga que el número de caminos (simples) de s a t en es al menosEntonces, es posible obtener una -cadenas de con ( y como puntos finales) por una secuencia de supresión y la contracción de los bordes?solstsol.solnortek.Ω(k)solst

Si la respuesta es positiva, la segunda parte de la pregunta es si existe un algoritmo eficiente para obtener una cadena tan grande.

Sería igualmente feliz con -chain o para cualquierkkαα>0.

Agradecería cualquier respuesta parcial o cualquier intuición sobre si tal conjetura debería ser válida.

Había publicado esto en el desbordamiento matemático hace unos días. Alguien sugirió publicarlo aquí también.

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

Raghav Kulkarni
fuente
Puede valer la pena revisar el gráfico de diamante recursivo para ver si es un contraejemplo. cstheory.stackexchange.com/questions/10169/…
Chandra Chekuri
Esa es una gráfica interesante. Aunque, me parece que esto puede no ser un contraejemplo para la " Conjetura de la cadena ". Sin embargo, esto puede ser para la " Conjetura de la cadena Ω ( k ) ". No estoy seguro todavía. kαΩ(k)
Raghav Kulkarni
No es un ejemplo contrario incluso para , porque si es un ejemplo de contador para Ω ( k ) entonces el grado de s es a lo sumo O ( k ) , y la longitud de los más largos s , t camino es O ( k ) , entonces no hay n k st rutas, excepto que suponemos que n = f ( k ) , este último caso, de nuevo es imposible (en realidad n es f (k) en esos gráficos, pero no conduce a una contradicción con el teorema, porque entonces fΩ(k)Ω(k)sO(k)s,tO(k)norteknorte=F(k)Fes función exponencial).
Saeed
Se publica un contraejemplo en MathOverflow: mathoverflow.net/questions/161451/… Todavía siento que la modificación "correcta" de la pregunta puede ser cierta, al menos para algunas clases de gráficos naturales, como los gráficos planos.
Raghav Kulkarni
Una variación posiblemente es esta: cada gráfico vinculado a contiene una cadena k , pero esta es una variación muy obvia. kk
Saeed

Respuestas:

2

Parece que este es un algoritmo FPT para una fija . En primer lugar, podemos considerar un bloque que contiene s , t . Si tenemos una cuadrícula menor de k × k que contiene s , t , entonces podemos encontrar la cadena correspondiente. De lo contrario, como Chekuri et al. se muestra, el gráfico tiene un ancho de árbol como máximo O ( k 1 / δ ) donde δ > 0ks,tk×ks,tO(k1/ /δ)δ>0 0Es algo constante. Entonces podemos calcular la descomposición del árbol del gráfico y luego verificar si esa cadena existe o no. No estoy seguro si con la programación dinámica habitual en gráficos de ancho de árbol acotado es posible encontrar la cadena. Además, si no se limita el ancho del árbol, su algoritmo puede encontrar la cuadrícula correspondiente en tiempo polinómico.

PD: Tenga en cuenta que no utilicé el hecho de que hay st caminos, puede ser por algún truco dentro de este hecho es posible obtener un mejor algoritmo.nortek

Saeed
fuente
Entonces, usted dice que la "cadena más grande que se puede obtener por eliminación-contracción" parece ser un parámetro fijo manejable. ¡Eso es interesante! Aunque, esto no dice nada acerca de la existencia de una gran cadena como consecuencia de tener una gran cantidad de caminos.
Raghav Kulkarni
@RaghavKulkarni, sí, creo que sí, aunque no estoy muy seguro, solo depende de que si es posible formular el problema como MSO_2 o proporcionar un enfoque de programación dinámica para el caso de ancho de árbol limitado, en realidad su problema parece estar en la categoría de problemas adicionales.
Saeed
Además, no necesitamos una cuadrícula muy grande como porque solo estamos buscando un caso pequeño, solo una ruta de 2 k , por lo que es posible mejorar el tiempo de ejecución (creo que mucho mejor, e incluso puede estar en P , Quiero decir, si algo como poly log k funciona, entonces es muy bueno o está en un algoritmo subexponencial FPT). K×K2kPAGS
Saeed