Hipergrafo crítico

En teoría de hipergrafos, el hipergrafo crítico o simplemente el crítico de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo σ(H) conformado por los subconjuntos de A tal que cada uno de sus elementos intersecan a una hiperarista de H diferente. Formalmente, dado un hipergrafo H definido sobre un conjunto base A, el crítico de H es el operador definido como:

$\sigma(\mathcal{H}):=\{Z\subseteq A; \forall a\in Z, \exists X\in\mathcal{H}\mbox{ con }X\cap Z=\{a\}\}$

Note que σ(H) es subconjunto del conjunto potencia del conjunto base, P(A).

El crítico de una estructura de hipergrafos G:=(H, K) se define como:

$\sigma(\mathcal{G}):=(\sigma(\mathcal{K}),\sigma(\mathcal{H}))$

y no σ(G):=(τ(K),τ(H)) como se podría pensar. Esto debido a que el operador crítico es antítono.

Complejidad computacional

Del punto de vista de complejidad computacional, determinar el crítico de un hipergrafo es un problema ineficiente, que crece exponencialmente en función del tamaño de la entrada (sea esta H o G). Sin embargo, determinar si una hiperarista dada pertenece o no a un hipergrafo crítico, sí es un problema resoluble en tiempo polinómico.

Referencias

• Polyméris, Andreas (2008). «Stability of two player game structures». Discrete Applied Mathematics 156 (14). ISSN 0166-218X, p. 2636-2646.