Ordenação topológica positiva, pegue 2

12

Este é um seguimento da recente pergunta de David Eppstein e é motivado pelos mesmos problemas.

Suponha que eu tenha um dag com pesos em número real em seus vértices. Inicialmente, todos os vértices são desmarcados. Posso alterar o conjunto de vértices marcados (1) marcando um vértice sem predecessores não marcados ou (2) desmarcando um vértice sem sucessores marcados. (Portanto, o conjunto de vértices marcados é sempre um prefixo da ordem parcial.) Quero encontrar uma sequência de operações de marcação / desmarcação que termine com todos os vértices marcados, de modo que o peso total dos vértices marcados seja sempre não negativo. .

  • Quão difícil é encontrar essa sequência de operações? Ao contrário do problema de David , nem está claro que esse problema esteja no NP; em princípio (embora eu não tenha nenhum exemplo) toda sequência de movimento legal pode ter tamanho exponencial. O melhor que posso provar é que o problema está no PSPACE.

  • A operação de desmarcação é realmente desnecessária? Se houver uma sequência de movimentação válida, deve haver uma sequência de movimentação válida que nunca desmarque um vértice? Uma resposta afirmativa tornaria esse problema idêntico ao de David . Por outro lado, se a desmarcação for necessária algumas vezes, deve haver um pequeno exemplo (tamanho constante) que a comprove.

Jeffε
fonte
1
Este artigo mostra que um problema
amplamente
Parece muito com um jogo de seixos: en.wikipedia.org/wiki/Pebble_game .
Warren Schudy 26/10/10
Um artigo recente sobre seixos : cs.utoronto.ca/~philipp/pages/papers/BWPebbling.pdf . O jogo de seixos pretos é semelhante ao seu, mas diferente, pois os nós intermediários podem ser desmarcados, mesmo que um sucessor seja marcado.
Warren Schudy 26/10/10

Respostas:

5

Em nosso seminário de pesquisa regular 666, apresentamos a seguinte prova.

Nos começamos com algumas definições. Seja P nosso poset. Para simplificar, suponha que nenhum dos pesos seja zero. Denote o peso de um vértice por w (x) e a soma dos pesos de um conjunto por w (X). Dizemos que um conjunto X é Y-up (fechado) se estiver contido em Y e todo elemento de Y que é maior que um elemento de X também está em X. Da mesma forma, diga que um conjunto X é Y-down se está contido em Y e todo elemento de Y menor que um elemento de X também está em X. Nesse idioma, o conjunto de elementos marcados deve estar sempre P-down.

Provamos por contradição. Pegue a sequência mais curta de marcação / desmarcação que marca todos os elementos. Chamamos essas seqüências completas. A qualquer momento, considere o conjunto de elementos que foram marcados antes, mas agora não estão marcados. Denote esse conjunto por U.

Reivindicação: w (U)> 0.

Prova: provamos que o peso de qualquer conjunto de U-up, X, é positivo. A prova é por indução no tamanho de X. Se houver um conjunto X-down, Y, tal que w (Y)> 0, então, como indução, sabemos que w (X \ Y)> 0 (pois é X-up), também temos w (X)> 0. Se para cada conjunto X-down, Y, temos w (Y) <0, excluindo até esse ponto todas as marcações e desmarcações dos elementos de X de nossa sequência, obtemos uma sequência completa mais curta. Terminamos a prova da reivindicação.

Agora suponha que tenhamos uma sequência completa em que w (U)> 0 a qualquer momento para o conjunto U de elementos atualmente não marcados. Pegue a sequência que obtemos disso, pegando a primeira marcação de cada elemento e nunca desmarcando nada. É claro que esta também será uma sequência completa, satisfazendo que o conjunto de elementos marcados seja sempre P-down. Além disso, a soma dos pesos será sempre pelo menos igual à da seqüência original, pois a qualquer momento a diferença é w (U). Acabamos.

Com esse método, pode-se até provar que, se em vez de marcar P inteiro, queremos apenas marcar um subconjunto de P, isso pode ser feito com uma sequência de marcações seguida por uma sequência de desmarcações. A prova é a mesma, exceto que, no final, alguns elementos, U, permanecem sem marcação, mas eles podem ser movidos para o final da sequência, pois o peso de qualquer configuração de U-up é positivo.

domotorp
fonte
1
Suas definições de Y-up e Y-down são idênticas. Presumivelmente, um subconjunto de X Y é Y-se para baixo a cada elemento de Y que é menor do que um elemento de X também é em X.
Jeffε
1
Muito legal! A resposta pode ser mais clara se a primeira linha indicar que afirmação você está provando. Acho que é uma prova de que a desmarcação nunca é necessária (se você puder resolvê-la usando desmarcação, poderá encontrar uma sequência que também a resolva sem desmarcar nada)? (E não, por exemplo, uma prova de que esse problema é difícil para NP / difícil para PSPACE ou para um algoritmo de tempo polinomial que pode decidir se existe ou não uma sequência de marcação).) Além disso, mais tarde na exposição em que diz "a qualquer momento", não estou claro se isso significa "em todos os pontos" ou "em algum momento"; Eu suspeito que você quer dizer o primeiro?
DW