¿Se puede muestrear eficientemente un vecino de un vértice en el gráfico de un politopo?

15

Tengo un politopo P definido por {x:Axb,x0} .

Pregunta: Dado un vértice v de P , ¿existe un algoritmo de tiempo polinómico para muestrear uniformemente de los vecinos de v en el gráfico de P ? (Polinomio en la dimensión, el número de ecuaciones y la representación de b . Puedo suponer que el número de ecuaciones es polinomial en la dimensión).

Actualización: creo que pude demostrar que esto es NP-hard, vea mi respuesta que explica el argumento. (Y por NP -hard, quiero decir que un algoritmo de tiempo polinomial probaría RP=NP ... no estoy seguro de cuál es la terminología correcta aquí).

Actualización 2: Hay una prueba de 2 líneas de dureza NP (dado el politopo combinatorio correcto) y pude encontrar un artículo de Khachiyan. Ver respuesta para descripción y enlace. :-RE


Un problema equivalente :

En los comentarios, Peter Shor señaló que esta pregunta es equivalente a la pregunta de si podemos muestrear uniformemente desde los vértices de un politopo dado. (Creo que la equivalencia es así: en una dirección, podemos pasar de un politopo P con un vértice v a la figura del vértice en v , P/v , y muestrear los vértices de P/v es equivalente a muestrear los vecinos de v en P En la otra dirección, podemos pasar de un politopo P a un politopo Q de una dimensión superior agregando un cono con vértice v y base P. Luego, muestrear los vecinos de v en Q es equivalente a muestrear los vértices de P ).

Esta formulación de la pregunta se ha hecho antes: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope


Lorenzo Najt
fuente
No sé la respuesta a su pregunta, pero que yo sepa, no hay una dureza NP conocida para muestrear uniformemente un vértice de un politopo dado explícitamente. Por ejemplo, aproximadamente los ciclos de muestreo son NP-duros. Sin embargo, si hubiera algún programa lineal cuyos vértices codifiquen ciclos, entonces es muy probable que pueda optimizar la duración del ciclo y así resolver Hamiltonian-Cycle.
Heng Guo
Otro comentario es que incluso si su pregunta tiene una respuesta positiva, no produce una muestra uniforme para los vértices (suponiendo la conjetura del politopo 0-1). El esqueleto del politopo en la mayoría de los casos interesantes no es regular, y los grados pueden variar exponencialmente.
Heng Guo
@HengGuo Gracias por los comentarios nuevamente, son muy útiles. ¿Conoces un buen ejemplo donde los grados varían exponencialmente? (No me sorprende que esto pueda suceder para los politopos generales; sería bueno tener un ejemplo combinatorio si supiera uno fuera de su cabeza.)
Lorenzo Najt
Considere el politopo conjunto independiente de un gráfico bipartito. Dos vértices (dos conjuntos independientes) están conectados si su diferencia simétrica induce un subgrafo conectado. Ahora, tome un gráfico bipartito cuyo lado tiene solo dos vértices, conecta a cada vértice del otro lado y v 2 solo uno. Considere los conjuntos independientes { v 1 } y { v 2 } . v1v2{v1}{v2}
Heng Guo
55
El muestreo uniforme de los vértices vecinos de un vértice dado de un politopo es el mismo problema que el muestreo uniforme de un vértice aleatorio de un politopo. Corta un cono infinitamente cerca del vértice. Luego, uno tiene un nuevo politopo, y si puede muestrear un vértice de este nuevo politopo, puede muestrear un vértice vecino del politopo original. Supongo que hacer esto aproximadamente está en BPP, pero no puedo encontrar ningún documento que lo pruebe.
Peter Shor

Respuestas:

4

Edición 2: Vergonzosamente, hay una prueba de dos líneas de la dureza NP , si una comienza con el politopo correcto.

Primero, recuerde que el politopo de circulación de un gráfico en la parte inferior de la página 4 de Generar todos los vértices de un poliedro es difícil .

Sus vértices están en correspondencia biyectiva con los ciclos simples dirigidos. Por lo tanto, son difíciles de muestrear o contar por la Propuesta 5.1 de JVV . :-RE

Equipado con estas palabras clave, pude encontrar la dureza del resultado del muestreo como teorema 1 de Hipergrafías transversales y familias de conos poliédricos de Khachiyan.


Editar: escribí el argumento a continuación, y parece correcto. Sin embargo, hay un argumento mucho más simple, que esbozaré aquí:

a) Mediante el análisis de algoritmos de retroceso para enumerar todos los vértices y todas las caras de un poliedro convexo (Fukuda et al.) es fuertemente NP-difícil resolver el siguiente problema en politopos:

Entrada: A polytope Ax=b,x0 en Rn un subconjunto Sn

Salida: Si hay un vértice v de P que es distinto de cero en cada una de las coordenadas en S .

b) Dado esto, se puede hacer la siguiente construcción: introducir nuevas variables yik para iS y k=1,,d , e introducir la desigualdad 0yikxi . Llame al politopo resultante PS,d . El objetivo de esta construcción es introducir un hipercubo sobre cada vértice, de dimensión d|supp(x)S|.

c) Se puede verificar que todos los vértices de este politopo estén por encima de los vértices del antiguo politopo y que el número de vértices sobre un vértice sea 2d|supp(x)S|, donde supp es la función que envía un vértice a las coordenadas donde no es cero.

d) Por un argumento habitual de tipo cadena de bigones, se deduce que al tomar d suficientemente grande, una muestra uniforme de los vértices de PS,d (con alta probabilidad) daría una muestra de los vértices maximizando el tamaño de su intersección con S .

Parece que hay varias extensiones de esto. Actualizaré con un enlace cuando finalice la escritura.


(El viejo argumento solía estar aquí, está en el historial de edición. Lo eliminé porque es muy largo e interferirá para encontrar la respuesta correcta a la pregunta).

Lorenzo Najt
fuente
Este es un argumento muy interesante! No verifiqué completamente todos los detalles en la parte 3) (¿cuáles son las funciones , H 0 , l e a v e s ?), Pero en principio, cualquier estructura que no se extienda solo puede incurrir en una explosión súper exponencial, que así se puede controlar tomando d polinomio grande. H1H0leavesd
Heng Guo
@HengGuo Gracias por leer! Por Me refiero a la cantidad de componentes, y | H 1 | la dimensión del espacio del ciclo (rango del circuito), y "deja" el número de vértices de grado 1. Agregaré esas definiciones. |H0||H1|
Lorenzo Najt
Debe haber algo mal con esto. Si hay un politopo cuyos vértices son lazos y ciclos simples, ¿no podemos usar la programación lineal para maximizar cualquier función lineal que queramos sobre este politopo? ¿Y eso no nos permitiría encontrar un lazo extendido en el tiempo polinómico?
Peter Shor el
@PeterShor Creo que esto no sucede porque el politopo vive dentro del hiperplano definido al establecer la suma de las variables de borde en una. De modo que funcional es constante sobre el politopo. La función que representa el número de aristas es el tamaño del soporte del vector, que no es lineal en este politopo.
Lorenzo Najt
@ PeterShor Agregué una prueba de que la función 'número de aristas' no puede ser lineal, vea la imagen en la parte inferior.
Lorenzo Najt