Título: Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
Directora: Flavia Bonomo
Consejero de estudios: Javier Marenco
Jurados:
Dr. Sergio Cabello Justo – Prof. Full, DMAT, Univ. de Liubliana
Dra. Paloma T. De Lima – Prof. Asis., Univ. de Copenhagen
Dr. Dimítrios Thilikós Touloupas – Dir. de Inv., CNRS – LIRMM

Resumen:
Intuitivamente, un problema localmente verificable es un problema de partición de vértices (o, equivalentemente, de coloreo de vértices) para el cual una solución puede ser verificada simplemente chequeando una determinada propiedad local para cada vértice, es decir, una propiedad que involucra solamente la solución restringida al vértice y a sus vecinos. Este es el caso de diversas variantes de los problemas de dominación, conjunto independiente y k-coloreo, entre otros. Existen numerosos marcos generales que incluyen un gran subconjunto de estos problemas, para los cuales se propusieron algoritmos para resolverlos eficientemente en varias clases de grafos.
En esta tesis definimos un nuevo marco para problemas localmente verificables, formalizando la noción intuitiva que tenemos de ellos para luego analizar bajo qué circunstancias podemos proponer algoritmos eficientes que los resuelvan. Los algoritmos propuestos se basan en programación dinámica y para ellos calculamos sus complejidades parametrizadas por treewidth, clique-width y mim-width. Los resultados obtenidos generalizan aquellos de marcos definidos anteriormente. Mostramos además cómo modelar dentro de nuestro marco diversos problemas de la literatura, como ser [k]-dominación romana, k-comunidad y dominación Grundy, probando así que son FPT o XP parametrizados por treewidth, clique-width o mim-width. Más aún, proponemos esquemas de aproximación polinomiales para algunos problemas localmente verificables en grafos planares.

Palabras claves: problema localmente verificable, treewidth, clique-width, mim-width, complejidad parametrizada, esquema de aproximación polinomial.