En teoría de grafos , una cobertura de vértices en un hipergrafo es un conjunto de vértices , de modo que cada hiperarista del hipergrafo contiene al menos un vértice de ese conjunto. Es una extensión de la noción de cobertura de vértices en un grafo. [1] : 466–470 [2]
Un término equivalente es un conjunto coincidente : dada una colección de conjuntos, un conjunto que interseca todos los conjuntos de la colección en al menos un elemento se denomina conjunto coincidente. La equivalencia se puede ver al mapear los conjuntos de la colección sobre hiperaristas.
Otro término equivalente, utilizado más en un contexto combinatorio , es transversal . Sin embargo, algunas definiciones de transversal requieren que cada hiperarista del hipergrafo contenga precisamente un vértice del conjunto.
Recordemos 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 llamados hiperaristas . Cada hiperarista puede contener uno o más vértices.
Una cubierta de vértice (también conocida como conjunto impactante o transversal ) en H es el conjunto T ⊆ V tal que, para todas las hiperaristas e ∈ E , se cumple que T ∩ e ≠ ∅ .
El número de cobertura de vértices (también conocido como número transversal ) de un hipergrafo H es el tamaño más pequeño de una cobertura de vértices en H. A menudo se denota por τ ( H ) . [1] : 466
Por ejemplo, si H es este hipergrafo 3-uniforme:
entonces H admite varias cubiertas de vértices de tamaño 2, por ejemplo:
Sin embargo, ningún subconjunto de tamaño 1 toca todas las hiperaristas de H. Por lo tanto, el número de cobertura de vértices de H es 2.
Nótese que volvemos al caso de cubiertas de vértices para gráficos simples si el tamaño máximo de las hiperaristas es 2.
Los problemas de cálculo conjunto mínimo de impacto y conjunto de impacto se definen como en el caso de los gráficos.
Si el tamaño máximo de una hiperarista está restringido a d , entonces el problema de encontrar un conjunto mínimo de d -impactos permite un algoritmo de aproximación a d . Suponiendo la conjetura de juegos únicos , este es el mejor algoritmo de factor constante que es posible y, de lo contrario, existe la posibilidad de mejorar la aproximación a d − 1 . [3]
Para el problema del conjunto de impacto, tienen sentido diferentes parametrizaciones . [4] El problema del conjunto de impacto es W [2] -completo para el parámetro OPT , es decir, es poco probable que exista un algoritmo que se ejecute en el tiempo f (OPT) n O (1) donde OPT es la cardinalidad del conjunto de impacto más pequeño. El problema del conjunto de impacto es manejable con parámetros fijos para el parámetro OPT + d , donde d es el tamaño del borde más grande del hipergrafo. Más específicamente, existe un algoritmo para el conjunto de impacto que se ejecuta en el tiempo d OPT n O (1) .
El problema de los conjuntos que chocan es equivalente al problema de la cobertura de conjuntos : una instancia de cobertura de conjuntos puede verse como un grafo bipartito arbitrario , con conjuntos representados por vértices a la izquierda, elementos del universo representados por vértices a la derecha y aristas que representan la inclusión de elementos en conjuntos. La tarea es entonces encontrar un subconjunto de cardinalidad mínima de vértices izquierdos que cubra todos los vértices derechos. En el problema de los conjuntos que chocan, el objetivo es cubrir los vértices izquierdos utilizando un subconjunto mínimo de vértices derechos. Por lo tanto, la conversión de un problema al otro se logra intercambiando los dos conjuntos de vértices.
Un ejemplo de una aplicación práctica que involucra el problema del conjunto de aciertos surge en la detección dinámica eficiente de la condición de carrera . [5] [6] En este caso, cada vez que se escribe en la memoria global, se almacenan el hilo actual y el conjunto de bloqueos mantenidos por ese hilo. Bajo la detección basada en conjuntos de bloqueos, si más tarde otro hilo escribe en esa ubicación y no hay una carrera, debe ser porque tiene al menos un bloqueo en común con cada una de las escrituras anteriores. Por lo tanto, el tamaño del conjunto de aciertos representa el tamaño mínimo del conjunto de bloqueos para estar libre de carrera. Esto es útil para eliminar eventos de escritura redundantes, ya que los conjuntos de bloqueos grandes se consideran poco probables en la práctica.
Una cobertura de vértices fraccionaria es una función que asigna un peso en [0,1] a cada vértice en V , de modo que para cada hiperarista e en E , la suma de las fracciones de vértices en e es al menos 1. Una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria en el que todos los pesos son 0 o 1. El tamaño de una cobertura de vértices fraccionaria es la suma de las fracciones de todos los vértices.
El número de cobertura de vértices fraccionarios de un hipergrafo H es el tamaño más pequeño de una cobertura de vértices fraccionarios en H . A menudo se denota por τ *( H ) .
Dado que una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria, para cada hipergrafo H :
número de cobertura de vértice fraccional ( H ) ≤ número de cobertura de vértice ( H );
En símbolos:
El número de vértices que cubren fracciones de un hipergrafo es, en general, menor que su número de vértices que cubren. Un teorema de László Lovász proporciona un límite superior para la relación entre ellos: [7]
Un plano proyectivo finito es un hipergrafo en el que cada dos hiperaristas se intersecan. Todo plano proyectivo finito es r -uniforme para algún entero r . Denotemos por H r el plano proyectivo r -uniforme. Se sabe que existen los siguientes planos proyectivos:
Cuando H r existe, tiene las siguientes propiedades: [8]
Una cubierta de vértice (transversal) T se llama mínima si ningún subconjunto propio de T es una transversal.
El hipergrafo transversal de H es el hipergrafo ( X , F ) cuyo conjunto de hiperaristas F consiste en todos los transversales mínimos de H .
El cálculo del hipergrafo transversal tiene aplicaciones en la optimización combinatoria , en la teoría de juegos y en varios campos de la informática , como el aprendizaje automático , la indexación de bases de datos , el problema de satisfacibilidad , la minería de datos y la optimización de programas informáticos .
