Defensa Tesis Licenciatura Javier Arregui

• Título: "Algoritmos eficientes para calcular el clique transversal mínimo en grafos"
• Director: Dr. Min Chih Lin
• Jurados:

  Dra. Flavia Bonomo - Universidad de Buenos Aires, Argentina

  Dra. Marina Groshaus - Universidad de Buenos Aires, Argentina

• Resumen:

Un clique transversal de un grafo G es un subconjunto de vértices que se intersecan con todos los cliques del grafo G. Es un problema NP-Hard determinar la cardinalidad (\tau_c(G)) del clique transversal de tamaño mínimo para un grafo G. En este trabajo proponemos algoritmos para generar un clique transversal de tamaño mínimo y por consiguiente determinar el valor de \tau_c(G), mejorando algunos resultados de (*) Durán, Lin, Mera y Szwarcfiter ("Algorithms for finding clique-transversals of graphs", Annals of Operations Research,157(1), 37–45 (2008)).

Los principales algoritmos con los que contribuimos en esta tesis son:

1) Un algoritmo general de tiempo O({n^{\tau_c(G)-1}m^{\frac{\tau_c(G)}{2}}}) que genera un clique transversal de tamaño mínimo para cualquier grafo G. Este algoritmo es una modificaci\'on del algoritmo propuesto en el trabajo mencionado (*) de tiempo O(n^{2\tau_c(G)}).

2) Un algoritmo robusto de tiempo O(n+m) que genera un clique transversal de tamaño mínimo para cualquier grafo arco-circular sin \overline{3K_{2}} como subgrafo inducido. Este algoritmo primero genera un modelo arco-circular a partir del grafo (cuesta tiempo O(n+m)) y luego lo utiliza para generar un clique transversal mínimo o bien detectar la existencia de un \overline{3K_2} como subgrafo inducido del grafo (todo esto cuesta tiempo O(n)). Por lo tanto, si la entrada del algoritmo ya es un modelo arco-circular del grafo, la complejidad total se reduce a O(n). El mejor algoritmo para esta clase de grafos hasta este momento era uno de tiempo O(n^{4}) propuesto en el mismo trabajo (*). Al igual que este algoritmo, nuestro algoritmo también es robusto en el sentido que si el grafo de entrada contiene alg\'un \overline{3K_2} como subgrafo inducido, o bien el algoritmo genera un clique transversal de tamaño mínimo del grafo o encuentra un subgrado inducido \overline{3K_2} en el grafo.

3) Un algoritmo de reconocimiento de tiempo O(nm^{\frac{3}{2}}) para los grafos arco-circulares sin \overline{3K_{2}}.

4) Un algoritmo de tiempo O(\tau_c(G)n m^{\frac{\tau_c(G)}{2}-1}(\tau_c(G)+\sqrt{m})) que genera un clique transversal de tamaño mínimo para cualquier grafo dualmente cordal G. Este algoritmo emplea la técnica llamada simplicial augmentation que fue introducida en (*) para grafos arco-circulares Helly.