Caracterização e Algoritmos para Generalização da Propriedade de Helly

Um hipergrafo é uma família de conjuntos especial que não possui dois conjuntos formados pelos mesmos elementos. Um hipergrafo H é (p,q,s)-Helly se todo hipergrafo parcial de H tal que cada p hiperarestas compartilham q elementos possui s elementos em sua interseção. Dizemos que H é p-Helly_k se todo hipergrafo parcial de H com até k hiperarestas é (p,1,1)-Helly; e que H é p-Helly forte se todo hipergrafo parcial H' de H possui p hiperarestas cuja interseção é igual à interseção de H'. Aplicando essas definições em grafos temos que um grafo G é (p,q)-clique-Helly se seu hipergrafo clique C(G) é (p,q,q)-Helly, que G é p-clique-Helly_k se C(G) é p-Helly_k, e que G é p-clique-Helly forte se C(G) é p-Helly forte. Neste trabalho apresentamos caracterizações para essas classes de hipergrafos e de grafos, as quais conduzem a algoritmos polinomiais para alguns casos. Para os outros casos apresentamos provas de NP-dificuldade.