UNAM
Usted está aquí: Inicio / Actividades académicas / Coloquios / Coloquio de Ciudad Universitaria / Actividades del Coloquio / Una dicotomía para el problema de los núcleos por H-caminos

Una dicotomía para el problema de los núcleos por H-caminos

Ponente: César Hernández
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.

archivado en: