Grafos {k}-romanos : estudio de la complejidad computacional de problemas de decisión asociados

Abstract

En esta tesis se plantean y abordan nuevos cuestionamientos en relación a una reciente variante (introducida en la literatura en 2016 y poco estudiada aún) de la dominación clásica en grafos definida y estudiada desde los años 50. El primer resultado general de esta tesis muestra que las clases de grafos {k}-romanos con k ⩾ 2, forman una secuencia no creciente de clases. Esto lleva a la pregunta de si existe un grafo {k}-romano para todo k ⩾ 2. Sin embargo se demuestra que este no es el caso. Como resultado principal de esta tesis, se demuestra que para todo k ⩾ 3, el problema de reconocer grafos {k}-romanos es NP-difícil, incluso cuando se restringe a la clase de grafos split. Para probar este resultado, se definen nuevos conceptos en el contexto de hipergrafos (estructuras que generalizan a los grafos). Como corolario se obtienen generalizaciones a hipergrafos de resultados muy relevantes en la literatura relativos a matchings y cubrimientos válidos para grafos. Por último, se muestran nuevos resultados de NP-completitud del problema de decisión asociado a la dominación {2}-romana, es decir el problema de decidir si para un grafo dado y un valor j fijo, existe una función {2}-romana dominante de peso j. En particular se prueba que este problema es NP-completo aún en grafos cordales, en grafos bipartitos planares, en grafos bipartitos cordales y grafos bipartitos con grado máximo 3.