Consideramos DAG (gráficos acíclicos dirigidos) com um nó de origem e um nó de destino ; arestas paralelas unindo o mesmo par de vértices são permitidas. Uma - corte é um conjunto de arestas cuja remoção destrói todos - caminhos mais longos do que ; mais curtos - caminhos, bem como longos caminhos "internos" (aqueles que não entre e ) pode sobreviver!t kt k s t s t
Pergunta: É suficiente remover no máximo cerca de de arestas de um DAG para destruir todos os caminhos - maiores que ?
Ou seja, se denota o número total de arestas em , todo DAG possui um corte com no máximo cerca de arestas? Dois exemplos:
- Se todos os caminhos - tiverem comprimento , existe um corte com arestas. Isto é porque então deve haver disjuntos -cuts: basta camada os nós de de acordo com sua distância da fonte nó .
- Se for um torneio transitivo (um DAG completo), também haverá um corte com arestas: corrija uma ordem topológica de nós, divida os nós em intervalos consecutivos de comprimento e remova todas as arestas que unem os nós do mesmo intervalo; isso destruirá todos os caminhos - maiores que . n / k s t k
Observação 1: Uma tentativa ingênua de dar uma resposta positiva (que eu também tentei como primeiro) seria para tentar mostrar que cada DAG deve ter cerca de disjuntos -cuts. Infelizmente, Exemplo 2 mostra que essa tentativa mal pode falhar: através de um argumento bom, David Eppstein tem mostrado que, para sobre , o gráfico não pode ter mais do que quatro disjuntos -cuts! √ Tn
Observação 2: É importante que um -cut só precisa destruir todas as longas - caminhos, e não necessariamente todos os caminhos longos. Nomeadamente, existem 1 DAGs nos quais todo corte "puro" (evitando arestas que incidem em ou ) deve conter quase todas as arestas. Então, minha pergunta é: a possibilidade de remover também arestas incidentes com ou reduz substancialmente o tamanho de um corte em ? Provavelmente, a resposta é negativa, mas ainda não consegui encontrar um contra-exemplo. s ts t s t k
Motivação: minha pergunta é motivada pela comprovação de limites mais baixos para redes monótonas de comutação e retificação. Essa rede é apenas um DAG, cujas bordas são rotuladas por testes "é ?" (não há testes ). O tamanho de uma rede é o número de bordas rotuladas. Um vetor de entrada é aceito, se houver um caminho - cujos testes sejam consistentes com esse vetor. Markov provou que, se uma função booleana monótona não possui mintermos menores que nenhum maxtermo menores que , então tamanho x i = 0 s tl w l ⋅ wé necessário. Uma resposta positiva à minha pergunta implicaria que são necessárias redes de tamanho sobre , se pelo menos variáveis tiverem que ser definidas como para destruir todos os mintermos com mais de .w k 0 k
1 A construção é apresentada neste documento. Tome uma árvore binária completa de profundidade . Remova todas as bordas. Para cada nó interno , desenhe uma aresta para de todas as folhas da subárvore esquerda de e uma aresta de para todas as folhas da subárvore direita de . Assim, a cada duas folhas de são conectadas por um caminho de comprimento no DAG. O próprio DAG possui nós e bordas, mas as bordas devem ser removidas para destruir todos os caminhos maiores que.
Respostas:
[Auto-resposta; esta é uma versão abreviada, a antiga pode ser encontrada aqui ]
Percebemos com Georg Schnitger que a resposta para minha pergunta é fortemente negativa : existem DAGs (mesmo em graus constantes), onde cada corte em deve ter uma fração constante de todas as arestas, não apenas uma fração de cerca de 1 / k , como em minha pergunta. (Um resultado ligeiramente mais fraco de que uma fração 1 / log k pode ser necessária, pode ser obtido usando uma construção muito mais simples mencionada na nota de rodapé acima. Uma breve descrição está aqui )k 1/k 1/logk
Nomeadamente, no artigo "Sobre redução de profundidade e grades" , Georg construiu uma sequência de gráficos acíclicos direcionados de grau máximo constante d em n = m 2 m de nós com a seguinte propriedade:Hn d n=m2m
Pegue agora dois novos nós e t e desenhe uma aresta de s para cada nó de H n e uma aresta de todos os nós de H n para t . O gráfico resultante L n ainda tem, no máximo, 2 n + d N = S ( n ) arestas.s t s Hn Hn t Gn 2n+dn=O(n)
Prova: chame os nós de nós internos de G n . Remova qualquer subconjunto de no máximo c ′ n arestas de G n , onde c ′ = c / 2 . Depois disso, remova um nó interno se houver incidente em uma borda removida. Observe que no máximo 2 c ′ n = c n nós internos são removidos. Nenhuma das arestas incidentes nos nós sobreviventes foi removida. Em particular, cada nó interno sobreviveram ainda está ligado a ambos os nós de s e tHn Gn c′n Gn c′=c/2 2c′n=cn s t . Pela propriedade acima de , não deve continuar a ser um caminho de comprimento 2 ε m que consiste inteiramente de nós internos sobreviveram. Como os pontos finais de cada um desses caminhos sobreviveram, cada um deles pode ser estendido para um caminho s - t em G n . QEDHn 2ϵm s t Gn
Uma conseqüência é triste: não existe nenhum análogo do lema de Markov para funções com muitos mintermos curtos , mesmo que o conjunto de mintermos longos possua alguma estrutura "complicada": não é possível provar o uso de limites inferiores super-lineares no tamanho da rede usando este argumento "comprimento vezes largura".
PS Esse argumento "comprimento vezes largura" (quando todos os caminhos - t são longos o suficiente) foi usado anteriormente por Moore e Shannon (1956). A única diferença é que eles não permitem retificações (arestas não identificadas). Portanto, esse é, de fato, um "argumento de Moore-Shannon-Markov".s t
fonte