Defensa Tesis Licenciatura Juan Carlos Terragno

• Título de la tesis: "Transversal y conjunto independiente de bicliques"
• Directora: Dra. Marina Groshaus
• Jurados:
  Dr. Fabio Protti - Universidade Federal Fluminense, Brasil
  Dr. Francisco Soulignac - Universidad de Buenos Aires, Argentina
  Lic. Leandro Montero - Universidad Parid Sud XI
• Resumen:

Los problemas de hallar el cardinal de un transversal de cliques mínimo y el cardinal de un conjunto independiente de cliques máximo se han estudiado extensamente en la literatura, tanto en el caso general como restringido a clases de grafos específicas.

Un transversal de cliques de un grafo G es un conjunto de vértices que cubren todas las cliques de G y un conjunto independiente de cliques de un grafo G es un conjunto de cliques de G tales que no comparten vértices entre sí.

Se ha demostrado que ambos problemas son NP-Hard o NP-Completos en grafos planares, grafos línea, grafos split, grafos totales, grafos de co-comparabilidad y grafos split clique-Helly hereditarios. Por otra parte, se ha demostrado que ambos problemas son resolubles en tiempo polinomial para grafos arco-circulares Helly, grafos fuertemente cordales, grafos balanceados, grafos de distancia hereditaria y grafos de comparabilidad.

Ambos problemas están estrechamente relacionados y se puede ver que para cualquier grafo G se cumple que el conjunto independiente de cliques máximo de G es mayor o igual que el transversal de cliques mínimo de G. En el caso de que valga la igualdad para todo grafo inducido de G, se dice que G es clique-perfecto.

Una biclique de un grafo G es un subgrafo inducido bipartito completo maximal con al menos una arista. El estudio de las bicliques ha tenido mucha atención en los últimos tiempos en diversos contextos y sus aplicaciones incluyen desde las redes sociales, hasta la genética y las matemáticas.

Motivados por los resultados existentes para los problemas de cliques, en esta tesis estudiamos dos problemas análogos en el contexto de las bicliques: hallar un transversal de bicliques mínimo y un conjunto independiente de bicliques máximo en diferentes clases de grafos.

Analizamos la complejidad de ambos problemas tanto en el caso general, como restringidos a grafos split, grafos planares, grafos bipartitos y grafos bloque. Estudiamos además la relación entre ambos parámetros y mostramos una clase de grafos para la cual la diferencia entre los parámetros es arbitrariamente grande, algunas clases biclique-perfectas y ejemplos de grafos minimalmente biclique-imperfectos.