Paseos $T$-Compatibles

Ponente(s): Kevin Axel Prestegui Ramos, Dr. Gerardo Miguel Tecpa Galván

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,\dots,n-1\}$ se tiene que $e_{i-1}e_i$ es una arista de $T(x_i)$. Stefan Szeider probó que determinar la existencia de una trayectoria compatible entre dos vértices de una gráfica con sistema de transición es un problema NP-Completo. Usando los resultados de Szeider, es posible demostrar que dado un vértice, determinar si dicho vértice se encuentra sobre un ciclo $T$-compatible también es un problema NP-Completo. A pesar de esto, en esta charla probamos que los problemas análogos concernientes a paseos $T$-compatibles y paseos cerrados $T$-compatibles, así como el problema de determinar si es posible partir el conjunto de aristas en paseos cerrados $T$-compatibles, son solubles en tiempo polinomial.