Cubiertas de vértice en hipergrafos

En teoría de grafos, una cubierta de vértice en un hipergrafo es un conjunto de vértices, tal que cada hiperarista del hipergrafo contiene al menos un vértice de dicho conjunto. Esta es una extensión de la idea de la cubierta de vértice en un grafo.: : 466–470 [1]​

Un término equivalente es el de un conjunto de golpe: dada una colección de conjuntos, si un conjunto el cuál tiene intersección no vacía con todos los demás conjuntos en la colección entonces le llamamos un conjunto de golpe. Podemos ver la equivalencia al mapear los conjuntos de nuestra colección hacia hiperaristas.

Otro término equivalente, utilizado en un contexto más combinatorio, es el de la transversal.

La ideas del conjunto de golpe y la cubierta de conjunto son equivalentes también.

Definición

Recuerda que un hipergrafo H es un par (V, E), donde V es un conjunto de vértices y E es un conjunto de subconjuntos de V a los cuales llamamos hiperaristas. Cada hiperarista puede contener uno o más vértices.

Un cubierta de vértice (aka conjunto de golpe o transversal) en H es un subconjunto T ⊆ V tal que, para cualquier hiperarista e ∈ E, sucede que T ∩ e ≠ ∅.

El número de cubierta de vértice (también conocido como número transversal) de un hipergrafo H es ldefinido como el tamaño más pequeño de una cubierta de vértice en H. Este número es a menudo denotado por ${\displaystyle \tau (H)}$.: : 466 

Por ejemplo, si H es el siguiente hipergrafo 3-uniforme:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Entonces H admite varias vértice-cubiertas de medida 2, Por ejemplo:

{1, 6}

Aun así, ningún subconjunto de tamaño 1 golpea a todas las hiperaristas de H. Por ello, el número de cubierta de vértice de H es 2.

Nota que volvemos el caso de cubiertas de vértice para grafos simples, si el tamaño mácimo de las hiperaristas es 2.

Algoritmos

Los problemas computacionales de mínimo conjunto de golpe y de conjunto de golpe estás definidossimilar a como en el caso de grafos.

Si la medida máxima de una hiperarista está restringida a d, entonces el problema de encontrar un mínimo d-conjunto de pegado permite un d-algoritmo de aproximación. Suponiendo la conjetura de juegos única, este es el algoritmo de factor constante mejor que es posible; de todos modos, hay la posibilidad de mejorar la aproximación a d − 1.[2]​

Para el problema del conjunto de golpe, diferentes parametrizaciones hacen sentido.[3]​ El problema de conjunto de pgolpe es W[2]-completo para el parámetro OPT; es decir, probablemente no puede encontrarse un algoritmo que corra en tiempo f(OPTA)n^{O(1)}, dónde OPT es la cardinalidad del conjunto de golpe más pequeño. El problema del conjunto del gople es tractable para parámetro fijo, para el parámetro OPT + d, donde d es el tamaño de la arista más grande del hipergrafo. Más específicamente, hay un algoritmo para el problema del conjunto del golpe que cprre en tiempo d^{OPT}nO(1).

Conjunto de golpe y cubierta de conjunto.

El problema del conjunto de golpe es equivalente al problema de cubierta del conjunto: Un caso de cubierta puesta puede ser visto como un grafo bipartito arbitrario, con sis conjuntos representados por vértices en el lado izquierdo, elementos del universo representados por vértices en el lado derecho, y las aristas que representan la inclusión de elementos en conjuntos. La tarea es entonces encontrar una cardinalidad mínima de un subconjunto de vértices del lado izquierdo, qué cubra todo del conjunto de vértices del lado derecho. En problema del conjunto del golpe, el objetivo es cubrir los vértices izquierdos, utilizando un subconjunto minimal de vértices derechos. Convirtiendo de un problema al otro es por tanto conseguido al intercambiar los dos conjuntos de vértices.

Aplicaciones

Un ejemplo de una aplicación práctica que implica el el problema del conjunto de golpe surge en detección dinámica eficaz de condición de carrera.[4]​ En este caso, cada vez la memoria global está escrita, el hilo actual de candados en dicho hilo son guardaos. Bajo detección basada en conjunto candado, si algún otro hilo escribe a aquella ubicación y no hay una carrera, tiene que ser porque lleva al menos un candado en común con cada uno de los récord previos. Por ello el tamaño del conjunto de golpe representa la medida de conjunto de cerradura mínima para ser carrera-libre. Esto es útil para eliminar eventos de sobreescritura redundante, ya que conjuntos de cerradura grande son considerados improbables en la práctica.

Cubierta de vértice fraccional

Una cubierta de vértice fraccionario es una función que asigna un peso en ${\displaystyle [0,1]}$ a cada vértice en V, tal que para cada hiperarista en E, la suma de fracciones de los vértices incidentes a e es al menos 1. Una cubierta de vértice es un caso especial de una cubierta de vértice fraccional, en la que todos pesos son o 0 o 1. El tamaño de un a cubierta fraccional de vértices es la suma de las fracciones de todos los vértices.

El número de cubierta de vértice fraccionario de un hypergrafo H es el tamaño más pequeño de una cubierta fraccional de vértices en H. Este número a menudo denotado por ${\displaystyle \tau ^{*}(H)}$.

Ya que una cubierta de vértice es un caso especial de una cubierta de vértices fraccional, entonces para cada hypergrafo H:

número-de cubierta de vértice fraccionario(H) ≤ número de cubierta de vértice(H);

En símbolos:

${\displaystyle \tau ^{*}(H)\leq \tau (H).}$

El número de cubierta de vértice fraccional de un hypergrafo es, en general, más pequeño que su número de cubierta de vértice. Un teorema de László Lovász proporciona una cuota superior para la proporción entre ellos:[5]​

• Si cada vértice está contenido en a lo sumo d hiperaristas (i.e., el grado del hipergrafo es como máximo d), entonces .${\displaystyle \tau (H)/\tau ^{*}(H)\leq 1+\ln(d)}$

Transversales en planos proyectivos finitos

Un plano proyectivo finito es un hipergrafo en que cada dos hyperaristas tienen intersección no vacía. Todo plano projectivo finito es r-uniforme para algún entero r. Denota por Hr el plano r-uniforme projectivo. Los siguientes planos proyectivos, sabemos que existen.

• H2: es simplemente un grafo de triángulo.
• H3: es el plano de Fano .
• Hp+1 existe siempre que p sea el poder de un número primo.

Cuándo Hr existe, tiene las propiedades siguientes:[6]​

• Hay ${\displaystyle r^{2}-r+1}$ vértices y r2-r+1 hyperedges.
• Es r-uniforme : cada hiperarista contiene exactamente r vértices.
• Es r-regular - cada vértice está contenido en exactamente r hyperedges.
• ${\displaystyle \tau (H_{r})=r}$: Los r vértices en cada hiperarista y son una vértice-cubierta de Hr (ya que cualquier otra arista se interseca con e).
• Las únicas transversales de tamaño r son las hiperaristas; cualquier otra transversal tiene trabajo r+2.
• .${\displaystyle \tau ^{*}(H_{r})=\nu ^{*}(H)=r-1+1/r}$
• ${\displaystyle \nu (H_{r})=1}$: Cada emparejando en Hr contiene como máximo una sola hiperarista.

Transversales mínimas

Un cubierta de vértice (transversal) T se es mínimal si ningún subconjunto propio de T es un transversal.

El hipergrafo transversal de H es el hipergrafo (X, F) cuyo conjunto de hiperaristas F consta de todas las transversales mínimas de H.

Computar el hipergrafo transversal tiene aplicaciones en optimización combinatoria, en teoría de juegos, y en varios campos de la informática tales como machine learning, indexación de bases de datos, el problema de satisfacibilidad, la minería de datos, y optimización de programa del ordenador.

Véase también

• Emparejando en hipergrafos @– habla también sobre la dualidad entre cubiertas de vértice y emparejamientos.

Referencias

1. Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland. 
2. Khot, Subhash; Regev, Oded (2008). «Vertex cover might be hard to approximate to within 2−ε». Journal of Computer and System Sciences 74 (3): 335-349. doi:10.1016/j.jcss.2007.06.019. 
3. Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Archivado desde el original el 18 de noviembre de 2007. Consultado el 5 de marzo de 2010. 
4. O'Callahan, Robert; Choi, Jong-Deok (2003). «Proceedings of the ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP 2003) and workshop on partial evaluation and semantics-based program manipulation (PEPM 2003)». Hybrid dynamic data race detectionACM SIGPLAN Notices 38 (10 edición): 167-178. doi:10.1145/966049.781528. 
5. Lovász, L. (1 de enero de 1975). «On the ratio of optimal integral and fractional covers». Discrete Mathematics (en inglés) 13 (4): 383-390. ISSN 0012-365X. doi:10.1016/0012-365X(75)90058-8. 
6. Füredi, Zoltán (1 de junio de 1981). «Maximum degree and fractional matchings in uniform hypergraphs». Combinatorica (en inglés) 1 (2): 155-162. ISSN 1439-6912. doi:10.1007/BF02579271. 

• Datos: Q2866200