Sesión Matemática DiscretaProblemas localmente verificables en grafos
Carolina Lucía Gonzalez
Instituto de Investigación en Ciencias de la Computación (UBA-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
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.
En esta presentación, la cual es una síntesis de los artículos [1,2,3], daremos una definición formal de lo que entendemos por problemas localmente verificables y estudiaremos bajo qué circunstancias podemos resolverlos eficientemente en distintas clases de grafos. Expresaremos su complejidad en función de los parámetros treewidth, clique-width y mim-width. Como consecuencia inmediata, podemos afirmar que múltiples problemas existentes en la literatura (por ejemplo, dominación Grundy, $k$-comunidad y $[k]$-dominación romana) se pueden resolver en tiempo polinomial en clases de grafos de treewidth acotada, clique-width acotada o mim-width acotada.
Trabajo en conjunto con: Narmina Baghirova (University of Fribourg, Suiza), Flavia Bonomo-Braberman (Instituto de Investigación en Ciencias de la Computación, UBA-CONICET, Argentina), Felix Mann (University of Fribourg, Suiza), Bernard Ries (University of Fribourg, Suiza) y David Schindl (University of Fribourg, Suiza).
Referencias
[1] N. Baghirova, C.L. Gonzalez, B. Ries y D. Schindl. Locally checkable problems parameterized by clique-width. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), 31:1-31:20, 2022.
[2] F. Bonomo-Braberman y C.L. Gonzalez. A new approach on locally checkable problems. Discrete Applied Mathematics, 314:53-80, 2022.
[3] C.L. Gonzalez y F. Mann. On $d$-stable locally checkable problems on bounded mim-width graphs. arXiv:2203.15724 [cs.DM], 2022.