Definición: Una " cadena " es un gráfico múltiple obtenido a partir de una ruta de longitud al duplicar cada borde.
Tenga en cuenta que el número de rutas entre dos puntos finales de una cadena es
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?
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 cualquier
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
fuente
Respuestas:
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 δ > 0k s , t k × k s , t O ( k1 / δ) δ> 0 Es 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
fuente
Los contraejemplos anteriores se publican en MathOverflow:
/mathpro/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor
/mathpro/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1
¿Alguna modificación "correcta" de la pregunta que aún sea cierta?
fuente