A questão a seguir está relacionada à otimização do algoritmo de programação dinâmica de caminho mais curto de Bellman-Ford - (consulte esta publicação para obter uma conexão). Além disso, uma resposta positiva implicaria que o tamanho mínimo de um programa de ramificação não determinístico monótono para o problema STCONN é . t
Deixe ser um DAG (dirigido gráfico acíclico) com um nó de origem e um nó de destino . Uma - corte é um conjunto de arestas, cuja remoção destrói todos - caminhos de comprimento ; supomos que existem tais caminhos em . Observe que caminhos - curtos não precisam ser destruídos.s t kt ≥ k G s t
Pergunta: Does deve ter pelo menos (cerca de) disjuntos -cuts? k
Se não houver caminhos - menores que , a resposta é SIM, porque temos o seguinte fato min-max (um duplo no teorema de Menger ) atribuído a Robacker . Um corte - é um corte para (destrói todos os caminhos - ).t kt k k = 1 t
Fato: Em qualquer gráfico direcionado, o número máximo de cortes - separados pela borda é igual ao comprimento mínimo de um caminho - . tt
Observe que isso é válido mesmo que o gráfico não seja acíclico.
Prova: trivialmente, o mínimo é pelo menos o máximo, pois cada caminho - cruza cada corte - em uma aresta. Para ver a igualdade, seja o comprimento de um caminho mais curto de a . Seja , para , e deixe ser o conjunto de arestas que deixam . É claro que os conjuntos são disjuntos, porque os conjuntos são tais. Portanto, resta mostrar que cada é um -t s t d ( u ) s u U r = { u : d ( u ) = r } r = 1 , … , d ( t ) E r U r E r U r E r s t s t p = ( u 1 , u 2 , … , u m )cortar. Para mostrar isto, levar um arbitrário - caminho com e . Como , a sequência de distâncias deve atingir o valor iniciando em e aumentando o valor em no máximo em cada etapa. Se algum valor for diminuído, devemos atingir o valor posteriormente. Portanto, deve haver um onde um salto de para acontece, significando a arestau m = t d ( u i + 1 ) ≤ d ( u i ) + 1 d ( u 1 ) , … , d ( u m ) d ( u m ) = d ( t ) d ( u 1 ) = d ( s ) = 0 1 d (d ( u i ) j d ( u j ) = r d ( u j + 1 ) = r + 1 ( u j , u j + 1 ) pertence a , conforme desejado. QED
Mas e se também houver caminhos mais curtos (que )? Alguma dica / referência?
JT Robacker, Teoremas Mín. Máx. das Correntes Mais Curtas e Cortes Separados de uma Rede, Memorando de Pesquisa RM-1660, The RAND Corporation, Santa Monica, Califórnia, [12 de janeiro] de 1956.
EDIT (um dia depois): Através de um argumento curto e muito agradável, David Eppstein respondeu à pergunta original acima em negativo : o DAG completo (um torneio transitivo ) não pode ter mais do que quatro -cuts disjuntos ! De fato, ele prova o seguinte fato estrutural interessante , para sobre . Um corte é puro se não contiver arestas incidentes em ou em .√t
Todo puro em contém um caminho de comprimento . T n k
Isto, em particular, implica que cada dois cortes puros devem se cruzar! Mas talvez ainda existam muitos cortes puros que não se sobrepõem "demais". Portanto, uma pergunta relaxada (as consequências para o STCONN seriam as mesmas ):k
Pergunta 2: Se todo corte puro tiver bordas , o gráfico deve ter bordas ? ≥ M Ω ( k ⋅ M )
A conexão com a complexidade do STCONN vem do resultado de Erdős e Gallai de que é necessário remover todas as bordas exceto de (não direcionado) , a fim de destruir todos os caminhos de comprimento . K m k
EDIT 2: Agora eu fiz a pergunta 2 no mathoverflow .