Caracterización y reconocimiento de los grafos clique de grafos arco-circulares Helly

MIN CHIH LIN; FRANCISCO J. SOULIGNAC; JAYME L. SZWARCFITER

Cordoba

Congreso; LVII Reunión anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2007

Un modelo arco-circular (CA) $mathcal{M} = (C,mathcal{A})$ es un conjunto de arcos $mathcal{A}$ per-te-ne-cien-tes a un c´{i}rculo $C$.  Si ning´un arco se encuentra contenido en otro arco, entonces $mathcal{M}$ es un modelo arco-circular propio (PCA) y cuando la familia de arcos satisface la propiedad de Helly, $mathcal{M}$ es un modelo arco-circular Helly (HCA). Si $mathcal{M}$ es a la vez propio y Helly, se dice que $mathcal{M}$ es arco-circular Helly propio (PHCA).  Un grafo es CA (PCA) (HCA) (PHCA) si es el grafo de intersecci´on de un modelo CA (PCA) (HCA) (PHCA).    Los grafos arco-circulares y sus subclases se encuentran muy estudiadas en la literatura.  Recientemente se encontraron algoritmos de reconocimiento lineales para estas clases, muchos de ellos con certificados.  En particular, para los grafos PHCA, Lin, Soulignac y Szwarcfiter dieron un algoritmo con certificados para el problema de reconocimiento que corre en tiempo $O(n)$ si se introduce como input un modelo PCA con los extremos ordenados.  En este caso $n$ denota la cantidad de arcos del modelo.  La salida del algoritmo es un modelo PHCA, si el grafo es PHCA, o un subgrafo inducido prohibido si no es PHCA.  Si en cambio se introduce como input un grafo, entonces primero hay que transformar grafo en tiempo $O(n+m)$ a un modelo PCA con el algoritmo con certificados de Kaplan y Nussbaum (basado en el de Deng, Hell y Huang), para obtener tiempo global $O(n+m)$.   Otra clase muy estudiada en la literatura es la de los grafos clique.  El grafo clique $K(G)$ de un grafo $G$ es el grafo de intersecci´on de su familia de cliques.  Un grafo $G$ es grafo clique (de una familia $mathcal{G}$) si existe otro grafo $H$ (perteneciente a $mathcal{G}$) tal que $G = K(H)$.  Recientemente Alc´on, Faria, Figueiredo y Guti´errez demostraron que el problema de determinar si un grafo es grafo clique es un problema NP-hard.  Sin embargo, para muchas subclases este problema se puede resolver en tiempo polinomial e incluso lineal.  Una de estas clases es la de los grafos de intervalos.  Hedman demostr´o que si $G$ es un grafo de intervalos, entonces $K(G)$ es un grafo de intervalos propio y que para todo grafo de intervalos propios $G$ existe $H in K^{-1}(G)$ que tambi´en es un grafo de intervalos propio.    La clase de los grafos de intervalos es una subclase de la clase de grafos HCA, y los de intervalos propios lo son con respecto a los PHCA.  En este trabajo demostramos un resultado similar al de Hedman para los grafos HCA y PHCA.  Demostramos que la clase de los grafos clique de grafos HCA es precisamente la clase de los grafos PHCA y que para todo grafo PHCA $G$ existe $K^{-1}(G)$ que es tambi´en PHCA.  En consecuencia, el problema de reconocimiento de estos grafos resulta lineal, ya que consiste ´unicamente en reconocer si el grafo es PHCA.  La preimagen PHCA tambi´en puede ser construida en tiempo lineal.