Resumen

Un subconjunto de vértices S se llama clique transversal si todo clique (completo maximal) del grafo contiene al menos un vértice de S. El problema consiste en hallar un clique transversal de menor cardinalidad del grafo. En estas dos charlas vamos a explicar por qué este problema es particularmente difícil y junto con otro problema llamado conjunto independiente de cliques (encontrar la mayor cantidad de cliques disjuntos de un grafo) definen una clase de grafos hereditaria denominada grafos t-perfectos. Examinamos algunas técnicas para reducir el problema a otros problemas más conocidos como dominación y clique-cover y en algunos casos pueden conducir a algoritmos polinomiales para algunas subclases de grafos. Presentamos también algoritmos para grafos generales. Finalmente, exhibimos algoritmos aproximados para algunas subclases de grafos donde el problema sigue siendo difícil (NP-Hard).