Pruebas de propiedad

El campo de la comprobación de propiedades de grafos fue introducido por primera vez por Goldreich, Goldwasser y Ron. En su artículo fundamental publicado en 1998, se analiza un problema abstracto de partición de grafos y se proporcionan algunos comprobadores. Estos incluyen como casos especiales varias propiedades importantes de grafos, como la bipartición , la k -colorabilidad , tener una gran camarilla y tener un gran corte . ^{[ 4 ]} En particular, los algoritmos naturales que muestrean un subgrafo y comprueban si satisface la propiedad son todos correctos, aunque con complejidades de consulta posiblemente subóptimas.

Desde entonces se han realizado varios descubrimientos relacionados.

• En 1992, Alon, Duke, Lefmann, Rödl y Yuster demostraron que para cada grafo H , la propiedad de no contener a H como subgrafo es comprobable. ^{[ 6 ]}
• En 1999, Alon, Fischer, Krivelevich y Szegedy demostraron que para cada grafo H , la propiedad de no contener H como subgrafo inducido es comprobable. ^{[ 7 ]}
• En 2005, Alon y Shapira demostraron que cualquier propiedad monótona de un grafo (una que se conserva bajo la eliminación de vértices y aristas) se puede comprobar con un error unilateral. ^{[ 8 ]}
• En 2008, Alon y Shapira presentaron probadores con error unilateral para todas las propiedades hereditarias de grafos. También caracterizaron propiedades que son fáciles de probar. Es decir, estas propiedades naturales son semihereditarias . Estas afirmaciones se aclararán más adelante. ^{[ 2 ]}

Una propiedad de un grafo es hereditaria si se conserva al eliminar vértices o, equivalentemente, si se conserva al tomar subgrafos inducidos . Algunas propiedades hereditarias importantes son la ausencia de H (para algún grafo H ), la k -colorabilidad y la planaridad . Todas las propiedades hereditarias son comprobables.

Teorema (Alon y Shapira 2008). Toda propiedad hereditaria de un grafo es comprobable con error unilateral. ^{[ 2 ]}

La demostración se basa en una versión del lema de eliminación de grafos para familias infinitas de subgrafos inducidos. La complejidad de la consulta utilizando este enfoque de regularidad es grande debido a la cota de la función torre en el lema de regularidad de Szemerédi .

Teorema (Lema de eliminación de grafos infinitos). Para cada conjunto (posiblemente infinito) de grafos H y ε > 0 , existen h ₀ y δ > 0 tales que, si G es un grafo de n vértices con menos de δ n ^{v ( H )} copias de H para cada H ∈ H con como máximo h ₀ vértices, entonces G puede hacerse H -libre inducido añadiendo/eliminando menos de ε n ² aristas. ^{[ 9 ]}

De manera informal, un probador despistado desconoce el tamaño de la entrada. Para una propiedad de grafo P , es un algoritmo que toma como entrada un parámetro ε y un grafo G , y luego se ejecuta como un algoritmo de prueba de propiedades en G para la propiedad P con parámetro de proximidad ε que realiza exactamente q ( ε ) consultas a G.

Definición. Un probador ciego es un algoritmo que toma como entrada un parámetro ε . Calcula un entero q ( ε ) y luego solicita a un oráculo un subgrafo inducido H con exactamente q ( ε ) vértices de G elegidos uniformemente al azar. Luego acepta o rechaza (posiblemente al azar) según ε y H. Decimos que prueba la propiedad P si acepta con una probabilidad de al menos 2/3 para G que tiene la propiedad P , y rechaza con una probabilidad de al menos 2/3 para G que está a ε -distancia de tener la propiedad P. ^{[ 2 ] [ 1 ] [ 10 ]}

Fundamentalmente, el número de consultas que realiza un evaluador desprevenido es una constante que depende únicamente de ε y no del tamaño del grafo de entrada G. En completa analogía con los algoritmos de prueba de propiedades, podemos hablar de evaluadores desprevenidos con error unilateral.

Podemos idear algunas propiedades del grafo para las cuales un evaluador debe acceder al número de vértices.

Ejemplo. Un grafo G satisface la propiedad P si es bipartito con un número par de vértices o perfecto con un número impar de vértices. ^{[ 2 ]}

En este caso, el evaluador ni siquiera puede diferenciar qué propiedad (bipartición o perfección) debe comprobar a menos que conozca el número de vértices. Existen numerosos ejemplos de propiedades tan inusuales. De hecho, la caracterización de las propiedades de grafos que puede comprobar un evaluador sin conocimiento previo del problema y con un error unilateral da lugar a una clase de propiedades naturales.

Definición. Una propiedad de grafo H es semihereditaria si existe una propiedad de grafo hereditaria H tal que cualquier grafo que satisfaga P satisface H , y para cada ε > 0 , existe un M ( ε ) tal que todo grafo de tamaño al menos M ( ε ) que esté ^a ε -distancia de satisfacer P contiene un subgrafo inducido que no satisface H. [ ^{2 ]}

De manera trivial, las propiedades hereditarias también son semihereditarias. Esta caracterización responde parcialmente a la inversa del otro teorema de Alon y Shapira mencionado anteriormente: las propiedades que son fáciles de probar (que tienen evaluadores inconscientes con error unilateral) son casi hereditarias. En el mismo artículo, demostraron que

Teorema (Alon y Shapira 2008). Una propiedad gráfica P tiene un probador de errores unilateral ajeno si y solo si P es semihereditaria. ^{[ 2 ]}

En esta sección, presentaremos algunos algoritmos de prueba naturales y ajenos a la lógica, con error unilateral, para la ausencia de triángulos , la bipartición y la k- colorabilidad . Son naturales en el sentido de que seguimos la idea natural de muestrear aleatoriamente un subconjunto X de vértices de G y comprobar si la propiedad del grafo se cumple en el subgrafo generado por X mediante una búsqueda exhaustiva . Tenemos un error unilateral, ya que estas propiedades son hereditarias: si G satisface la propiedad, también debe hacerlo el subgrafo generado por X , por lo que nuestro algoritmo de prueba siempre la acepta.

Para la ausencia de triángulos , el probador es una aplicación del lema de eliminación de triángulos . En particular, nos dice que si el grafo G está ε -lejos de estar libre de triángulos, entonces hay una constante (computable) δ = δ ( ε ) tal que G tiene al menos δ n ³ triángulos.

Ejemplo (Algoritmo de prueba de ausencia de triángulos).

1. Dado el grafo G , elija un conjunto aleatorio X de q ( ε ) = 1/ δ tríos de vértices de forma independiente y aleatoria, donde δ es como se indicó anteriormente.
2. Para cada triplete de vértices en X , consulte si los tres pares de vértices son adyacentes en G.
3. El algoritmo acepta si ninguna tripleta de vértices induce un triángulo, y rechaza en caso contrario. ^{[ 1 ]}

Para la bipartición y la k- colorabilidad , sea δ el límite superior deseado para la probabilidad de error en los siguientes evaluadores. Cabe señalar que la complejidad de la consulta no debe confundirse con el tiempo de ejecución. Este último suele ser exponencial (como ocurre en ambos casos) debido a la falta de un algoritmo de decisión de tiempo polinomial para evaluar la propiedad en el subgrafo inducido. En su lugar, realizamos una búsqueda por fuerza bruta . ^{[ 4 ]}

Ejemplo (Algoritmo de prueba bipartita).

1. Dado el grafo G , elija un conjunto aleatorio X de q ( ε ) = O (log(1/( ε δ ))/ ε ² ) vértices.
2. Para cada par de vértices en X , consulte si son adyacentes en G.
3. Acepta si el subgrafo inducido de G en X es bipartito y rechaza en caso contrario. ^{[ 4 ]}

Ejemplo (algoritmo de prueba de k-colorabilidad).

1. Dado el grafo G , elija un conjunto aleatorio X de q ( ε ) = O ( k ⁴ log ² ( k / δ )/ ε ³ ) vértices.
2. Para cada par de vértices en X , consulta si son adyacentes en G.
3. Acepta si el subgrafo inducido de G en X es k-coloreable y rechaza en caso contrario. ^{[ 4 ]}