Una dicotomía para el problema de los núcleos por H-caminos
Institución: IM-UNAM
Tipo de Evento: Investigación
Cuándo |
03/05/2016 de 12:00 a 13:00 |
---|---|
Dónde | Auditorio "Alfonso Nápoles Gándara" |
Agregar evento al calendario |
vCal iCal |
Resumen:
Dada una digráfica H, posiblemente con lazos, decimos que una segunda digráfica, D, está H-coloreada por flechas si las flechas de D están coloreadas con los vértices de H. Un H-camino en D es un camino dirigido en D en el que los colores de cualesquiera dos flechas
consecutivas corresponden con una flecha de H. Dados dos vértices u,v en D, decimos que u alcanza a v por H-caminos si existe un
H-camino en D con vértice inicial u y vértice final v. Un núcleo por H-caminos de D es un subconjunto, K, del conjunto de vértices de D
que es independiente por H-caminos (ningún vértice de K alcanza a otro por H-caminos) y es absorbente por H-caminos (para todo vértice
en el complemento de S existe un vértice en S al cual alcanza por H-caminos).
Recientemente, Hortensia Galeana y Ricardo Strausz caracterizaron a las digráficas H para las que cualquier digráfica D, H-coloreada por
flechas, tiene un núcleo por H-caminos, mismas que llamaron patrones pancromáticos. Nuestro trabajo consiste en demostrar que para
cualquier digráfica H que no es un patrón pancromático, el problema de determinar si una digráfica H-coloreada por flechas, D, tiene núcleo
por H-caminos, es NP-completo. Para este fin daremos una caracterización de los patrones pancromáticos mediante una familia finita de subdigráficas prohibidas, y construiremos una familia de reducciones polinomiales para demostrar que para cualquier elección de H (que no sea un patrón pancromático), el problema de determinar la existencia de núcleos por H-caminos es NP-difícil. Por otro lado, proponemos un algoritmo para verificar, en tiempo polinomial, si un conjunto dado es un núcleo por H-caminos en una digráfica D, con lo que verificamos que nuestro problema está en la clase NP.