Pode-se amostrar de maneira eficiente e uniforme um vizinho de um vértice no gráfico de um politopo?

15

Eu tenho um politopo P definido por {x:UMAxb,x0 0} .

Pergunta: Dado um vértice v de P , existe um algoritmo de tempo polinomial para amostrar uniformemente os vizinhos de v no gráfico de P ? (Polinômio na dimensão, o número de equações e a representação de b . Posso assumir que o número de equações é polinomial na dimensão.)

Atualização: acho que consegui mostrar que isso é difícil para o NP; veja minha resposta que explica o argumento. (E por NP -Hard, quero dizer que um algoritmo de tempo polinomial provaria RP=NP ... não sei o que a terminologia correta é aqui.)

Update 2: Não é uma prova de 2 linhas de NP -hardness (dada a polytope combinatória direita) e eu era capaz de encontrá-lo um artigo de Khachiyan. Veja a resposta para descrição e link. :-D


Um problema equivalente :

Nos comentários, Peter Shor apontou que essa pergunta é equivalente à questão de saber se podemos amostrar uniformemente a partir dos vértices de um dado polítopo. (Eu acho que a equivalência é assim: em uma direção, podemos ir de um polítopo P com um vértice v para a figura do vértice em v , P/v , e amostrar os vértices de P/v é equivalente a amostrar os vizinhos de v em P Na outra direção, podemos ir de um polítopo P a um polítopo Q de uma dimensão superior, adicionando um cone com vértice v e base P. Então amostrar os vizinhos de v em Q é equivalente a amostrar os vértices de P )

Esta formulação da pergunta já foi feita antes: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope


Lorenzo Najt
fonte
Não sei a resposta para sua pergunta, mas, pelo que sei, não há dureza NP conhecida para amostrar uniformemente um vértice de um polítopo explicitamente. Por exemplo, aproximadamente ciclos de amostragem são difíceis de NP. No entanto, se houvesse algum programa linear cujos vértices codificassem ciclos, é muito provável que você possa otimizar a duração do ciclo e, assim, resolver o ciclo Hamiltoniano.
Heng Guo
Outra observação é que, mesmo que sua pergunta tenha uma resposta positiva, ela não produz um amostrador uniforme para os vértices (assumindo a conjectura do polítopo 0-1). O esqueleto do politopo, na maioria dos casos interessantes, não é regular e os graus podem variar exponencialmente.
Heng Guo
@HengGuo Obrigado pelos comentários novamente, eles são muito úteis. Você conhece um bom exemplo em que os graus variam exponencialmente? (Não estou surpreso que isso pode acontecer para polytopes gerais, seria bom ter um exemplo combinatória se sabe de um fora do topo de sua cabeça.)
Lorenzo Najt
Considere o conjunto polítopo independente de um gráfico bipartido. Dois vértices (dois conjuntos independentes) são conectados se sua diferença simétrica induzir um subgráfico conectado. Agora, pegue um gráfico bipartido cujo lado tenha apenas dois vértices, conecta a todos os vértices do outro lado e v 2 apenas um. Considere conjuntos independentes { v 1 } e { v 2 } . v1v2{v1}{v2}
Heng Guo
5
A amostragem uniforme dos vértices vizinhos de um dado vértice de um polítopo é o mesmo problema que a amostragem uniforme de um vértice aleatório de um politopo. Pique um cone infinitamente próximo ao vértice. Um deles possui um novo polítopo e, se você pode experimentar um vértice desse novo polítopo, pode experimentar um vértice vizinho do polítopo original. Eu acho que fazer isso aproximadamente está no BPP, mas não consigo encontrar nenhum documento que prove isso.
31519 Peter S. Shor

Respostas:

4

Editar 2: Embaraçosamente, existe uma prova duas linhas do NP -hardness, se se começar com o poliepítopo direita.

Primeiro, lembre-se de que o polítopo de circulação de um gráfico na parte inferior da página 4 de Gerar todos os vértices de um poliedro é difícil .

Seus vértices estão em correspondência bijetiva com os ciclos simples direcionados. Portanto, eles são difíceis de amostrar ou contar pela Proposição 5.1 da JVV . :-D

Equipado com essas palavras-chave, pude encontrar a dureza do resultado da amostragem como teorema 1 dos Higrógrafos Transversais e Famílias de Cones Poliédricos de Khachiyan .


Edit: Eu escrevi o argumento abaixo, e parece correto. No entanto, há um argumento muito mais simples, que descreverei aqui:

a) Pela análise dos algoritmos de backtrack para listar todos os vértices e todas as faces de um poliedro convexo (Fukuda et al.), é altamente NP difícil resolver o seguinte problema nos politopos:

Entrada: Um polítopo Ax=b,x0 no Rn um subconjunto Sn

Saída: Se há um vértice v de P que é diferente de zero em cada uma das coordenadas em S .

b) Dado isso, pode-se fazer a seguinte construção: introduzir novas variáveis yik para iS e k=1,,d , e introduzir a desigualdade 0yikxi . Chame o polítopo resultantePS,d . O objetivo dessa construção é introduzir um hipercubo acima de cada vértice, da dimensãod|supp(x)S|.

c) Pode-se verificar se todos os vértices deste polítopo estão todos acima dos vértices do polítopo antigo e se o número de vértices sobre um vértice é 2d|supp(x)S|, em que supp é a função que envia um vértice para as coordenadas em que é diferente de zero.

d) Por uma corrente usual de argumento do tipo bigons, segue-se que, tomando d suficientemente grande, uma amostra uniforme dos vértices de PS,d daria (com alta probabilidade) uma amostra dos vértices, maximizando o tamanho de sua interseção com S .

Parece haver várias extensões disso. Vou atualizar com um link quando a escrita estiver concluída.


(O argumento antigo costumava estar aqui - está no histórico de edições. Eu o removi porque é muito longo e interfere na localização da resposta correta para a pergunta.)

Lorenzo Najt
fonte
Este é um argumento muito interessante! Não verifiquei completamente todos os detalhes na parte 3) (quais são as funções , H 0 , l e a vH1H0 ?), Mas, em princípio, qualquer estrutura não abrangendo só pode incorrer em uma explosão exponencial super, que assim, pode ser controlado tomando d polinomial grande. leavesd
Heng Guo
@HengGuo Obrigado pela leitura! por Quero dizer o número de componentes e | H|H0|a dimensão do espaço do ciclo (classificação do circuito) e "deixa" o número de vértices do grau 1. Vou adicionar essas definições. |H1|
Lorenzo Najt 22/04/19
Deve haver algo errado com isso. Se existe um politopo cujos vértices são lassos e ciclos simples, não podemos usar a programação linear para maximizar qualquer função linear que desejamos sobre esse politopo? E isso não nos deixaria encontrar um laço estendido no tempo polinomial?
Peter Shor
@ PeterShor Acho que isso não acontece porque o politopo mora dentro do hiperplano definido pela definição da soma das variáveis ​​de borda como uma. Portanto, esse funcional é constante sobre o politopo. A função que representa o número de arestas é o tamanho do suporte do vetor, que não é linear neste politopo.
Lorenzo Najt 25/04/19
@ PeterShor Adicionei uma prova de que a função 'número de arestas' não pode ser linear; veja a figura na parte inferior.
Lorenzo Najt 25/04/19