Título: Representación numérica de modelos arco-circulares propios
Director: Dr. Francisco Soulignac
Jurados: Dr. Luerbio Faria, Dra. Ana Ferreira Da Silva, Dr. Luciano Grippo

Link al evento: https://youtube.com/live/H4bl664rR_I?feature=share

Resumen: Un modelo arco-circular propio (PCA) es un par M=(C,A) donde
C es un círculo con un punto 0 y A es un conjunto de arcos de C donde
ningún arco contiene a otro. El modelo M es equivalente a otro modelo
PCA M’ cuando los extremos de los arcos de M aparecen en el mismo
orden que aquellos de los arcos de M’ si se recorren sus círculos en
sentido horario desde el 0. Si todos los arcos de M tienen longitud l
y sus extremos están a distancia al menos 1, entonces M es un modelo
(|C|,l)-CA. El problema de representación unitaria (Rep) pregunta si
existe un modelo (c,l)-CA equivalente a un modelo PCA M dado, para
algún c y l.

En esta Tesis abordamos Rep modelando cada instancia como un sistema
de inecuaciones lineales R que tiene un digrafo toroidal S asociado.
Así, derivamos un algoritmo certificante para resolver Rep más simple
que los conocidos en la literatura. Además, analizando la
representación toroidal de S, demostramos que los vértices de la
región factible de R son enteros. Este resultado implica la
tratabilidad computacional del problema de representación minimal
(MinUCA), donde buscamos un modelo (c,l)-CA equivalente a un modelo de
entrada M que minimice c y l. Diseñamos un algoritmo que resuelve
MinUCA en tiempo O(n^3) y espacio O(n^2).

Más allá de MinUCA, definimos el problema de representación mínima
(IsoMinUCA), donde, dado un modelo PCA M, buscamos un modelo (c,l)-CA
cuyo grafo de intersección sea isomorfo al de M, minimizando c y l.
Demostramos que IsoMinUCA está bien definido y que es NP-Completo.

Finalmente, estudiamos k-Mult, una generalización de Rep que consiste
en determinar si un modelo PCA M es k-multiplicativo. Intuitivamente,
tenemos que encontrar un modelo (c,l)-CA tal que al extender q veces
la longitud de sus arcos se obtenga un modelo de la q-ésima potencia
de M, para todo q <= k.