Seminario de becarios: septiembre 2024

Sean G una gráfica, para cada v en V(G), T(v) denota una gráfica cuyo conjunto de vértices son las aristas incidentes en v y T la familia de las gráficas T(v). En tal caso, decimos que G es una gráfica con sistema de transición T. Un camino W = (x_0,e_0,x_1,...,x_n-1,e_n-1,x_n) es T-compatible si para cada i en {1,...,n-1} se tiene que e_i-1e_i es una arista de T(x_i).

Jan Kratochvil y Svatopluk Poljak demostraron que dada una gráfica con sistema de transición T, es un problema NP-Completo decidir si G contiene un 2-factor T-compatible (es decir, una subgráfica generadora 2-regular compuesta por ciclos T-compatibles). Más adelante, Stefan Szeider probó que dados dos vértices u y v de una gráfica con sistema de transición T, determinar la existencia de una uv-trayectoria T-compatible es un problema NP-Completo. A pesar de estos resultados referentes a NP-Completitud, probamos que encontrar un paseo T-compatible entre dos vértices, o determinar que no existe, es soluble en tiempo polinomial. Más aún, demostramos que también es posible encontrar un paseo T-compatible de longitud mínima entre dos vértices cualesquiera en tiempo polinomial. Del mismo modo, mostramos que el problema de encontrar una descomposición en paseos cerrados T-compatibles con la mayor cantidad de aristas también es un problema soluble en tiempo polinomial.