En la teoría de grafos , la cobertura de un vértice en un hipergráfico es un conjunto de vértices, de modo que cada hipergráfico del hipergráfico contiene al menos un vértice de ese conjunto. Es una extensión de la noción de cobertura de vértices en un gráfico . [1] : 466–470 [2]
Un término equivalente es un conjunto de impacto : dada una colección de conjuntos, un conjunto que interseca todos los conjuntos de la colección en al menos un elemento se llama conjunto de impacto. La equivalencia se puede ver mapeando los conjuntos de la colección en hipermercados.
Otro término equivalente, usado más en un contexto combinatorio, es transversal .
Las nociones de golpear el set y cubrir el set también son equivalentes.
Definición
Recuerde que un hipergráfico H es un par ( V , E ), donde V es un conjunto de vértices y E es un conjunto de subconjuntos de V llamados hiperredges . Cada hiperredge puede contener uno o más vértices.
Una cobertura de vértice (también conocida como conjunto de golpe o transversal ) en H se establece T ⊆ V de modo que, para todas las hiperfuertes e ∈ E , se sostiene que T ∩ e ≠ ∅.
El número de vértice de la cubierta (también conocido como número transversal ) de un hypergraph H es el tamaño más pequeño de una cubierta de vértice en H . A menudo se denota por. [1] : 466
Por ejemplo, si H es este hipergrama de 3 uniformes:
- {{1,2,3}, {1,4,5}, {4,5,6}, {2,3,6}}
entonces H admite varias cubiertas de vértices de tamaño 2, por ejemplo:
- {dieciséis}
Sin embargo, ningún subconjunto de tamaño 1 Resultados todos los hyperedges de H . Por tanto, el número de cobertura de vértice de H es 2.
Tenga en cuenta que recuperamos el caso de las cubiertas de vértices para gráficos simples si el tamaño máximo de los hipermercados es 2.
Algoritmos
Los problemas de cálculo mínimo conjunto de aciertos y conjunto de aciertos se definen como en el caso de los gráficos.
Si el tamaño máximo de un hyperedge se limita a D , entonces el problema de encontrar un mínimo d -hitting conjunto permite una d : Aproximación algoritmo. 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 ad - 1. [3]
Para el problema del conjunto de golpes, diferentes parametrizaciones tienen sentido. [4] El problema del conjunto de aciertos es W [2] -completo para el parámetro OPT, es decir, es poco probable que haya un algoritmo que se ejecute en el tiempo f (OPT) n O (1) donde OPT es la cardinalidad del conjunto de bateo más pequeño. El problema del conjunto de golpes se puede tratar con parámetros fijos para el parámetro OPT + d , donde d es el tamaño del borde más grande del hipergráfico. Más específicamente, existe un algoritmo para golpear el conjunto que se ejecuta en el tiempo d OPT n O (1) .
Golpear set y set cover
El problema del conjunto impactante es equivalente al problema de cobertura de conjunto : una instancia de cobertura de conjunto puede verse como un gráfico 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 del conjunto de golpes, el objetivo es cubrir los vértices izquierdos utilizando un subconjunto mínimo de los vértices derechos. Por lo tanto, la conversión de un problema a otro se logra intercambiando los dos conjuntos de vértices.
Aplicaciones
Un ejemplo de una aplicación práctica que implica el problema del conjunto de golpes surge en la detección dinámica eficiente de la condición de carrera . [5] En este caso, cada vez que se escribe la memoria global, se almacenan el hilo actual y el conjunto de bloqueos mantenidos por ese hilo. Bajo la detección basada en la cerradura, si más tarde otro hilo escribe a ese lugar y hay no 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 golpes representa el tamaño mínimo del conjunto de bloqueo para que no tenga carreras. Esto es útil para eliminar eventos de escritura redundantes, ya que los conjuntos de bloqueos grandes se consideran poco probables en la práctica.
Cobertura de vértice fraccionada
Una cobertura de vértice fraccionaria es una función que asigna un peso ena cada vértice en V , de modo que para cada hiperredge e en E , la suma de fracciones de vértices en e es al menos 1. Una cobertura de vértice es un caso especial de una cobertura de vértice fraccional en la que todos los pesos son 0 o 1. El tamaño de la cobertura de un vértice fraccional es la suma de las fracciones de todos los vértices.
El número de vértice de la cubierta fraccional de un hypergraph H es el tamaño más pequeño de un vértice de la cubierta fraccional en H . A menudo se denota por.
Dado que una cobertura de vértice es un caso especial de una cobertura de vértice fraccional, para cada hipergráfico 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 cobertura de vértice fraccional de un hipergráfico es, en general, más pequeño que su número de cobertura de vértice. Un teorema de László Lovász proporciona un límite superior en la relación entre ellos: [6]
- Si cada vértice está contenido como máximo en d hiperedges (es decir, el grado del hipergráfico es como máximo d ), entonces.
Transversales en planos proyectivos finitos
Un plano proyectivo finito es un hipergrafo en el que se cruzan cada dos hipergrafias. Todo plano proyectivo finito es r -uniforme para algún número entero r . Denote por H r el plano proyectivo uniforme r . Se sabe que existen los siguientes planos proyectivos:
- H 2 : es simplemente un gráfico triangular.
- H 3 : es el avión Fano .
- H p + 1 existe siempre que p es la potencia de un número primo.
Cuando existe H r , tiene las siguientes propiedades: [7]
- Tiene r 2 - r +1 vértices y r 2 - r +1 hipermercados.
- Es r -uniforme: cada hiperredge contiene exactamente r vértices.
- Es r -regular: cada vértice está contenido exactamente en r hiperexpresiones.
- : los r vértices en cada hiperredge e son una cubierta de vértice de H r (ya que todas las demás hiperredge intersectan e ).
- Las únicas transversales de tamaño r son las hiperterias; todos los demás transversales tienen un tamaño de al menos r +2.
- .
- : cada coincidencia en H r contiene a lo sumo un solo hiperredge.
Transversales mínimas
Una cobertura de vértice (transversal) T se llama mínima si ningún subconjunto propio de T es una transversal.
El hypergraph transversal de H es la hypergraph ( X , F ) cuyo conjunto hyperedge F consta de todos los mínimos-transversales de H .
La computación del hipergrama 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 la satisfacibilidad , la minería de datos y la optimización de programas informáticos .
Ver también
- Emparejamiento en hipergráficos : analiza también la dualidad entre cobertura de vértices y emparejamiento.
Referencias
- ^ a b Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ Berge, Claude (1973). Gráficos e hipergráficos . Amsterdam: Holanda Septentrional.
- ^ Khot, Subhash ; Regev, Oded (2008). "La cobertura del vértice puede ser difícil de aproximar dentro de 2 − ε". Revista de Ciencias de la Computación y Sistemas . 74 (3): 335–349. doi : 10.1016 / j.jcss.2007.06.019 .
- ^ Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Saltador. ISBN 978-3-540-29952-3. Consultado el 5 de marzo de 2010 .
- ^ O'Callahan, Robert; Choi, Jong-Deok (2003). "Detección de carrera de datos dinámicos híbridos" . Actas del simposio ACM SIGPLAN sobre principios y práctica de la programación paralela (PPoPP 2003) y taller sobre evaluación parcial y manipulación de programas basada en semántica (PEPM 2003) . Avisos ACM SIGPLAN . 38 (10). págs. 167-178. doi : 10.1145 / 966049.781528 .
- ^ Lovász, L. (1 de enero de 1975). "Sobre la relación de coberturas integrales y fraccionarias óptimas" . Matemáticas discretas . 13 (4): 383–390. doi : 10.1016 / 0012-365X (75) 90058-8 . ISSN 0012-365X .
- ^ Füredi, Zoltán (1 de junio de 1981). "Grado máximo y emparejamientos fraccionarios en hipergráficos uniformes" . Combinatorica . 1 (2): 155-162. doi : 10.1007 / BF02579271 . ISSN 1439-6912 . S2CID 10530732 .