Quantos cortes de borda disjuntos um DAG deve ter?

10

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 é . tstΘ(n3)

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 kGstkt k G s tstkGst

Pergunta: Does deve ter pelo menos (cerca de) disjuntos -cuts? kGk 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 kstkt k k = 1stkk=1 tst

Fato: Em qualquer gráfico direcionado, o número máximo de cortes - separados pela borda é igual ao comprimento mínimo de um caminho - . tsttst

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 )ststd(u)suUr={u:d(u)=r}r=1,,d(t)ErUrErUrErstcortar. 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 arestastp=(u1,u2,,um)u 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 (u1=sum=td(ui+1)d(ui)+1d(u1),,d(um)d(um)=d(t)d(u1)=d(s)=01d ( u i ) j d ( u j ) = r d ( u j + 1 ) = r + 1 ( u j , u j + 1 )d(ui)d(ui)jd(uj)=rd(uj+1)=r+1(uj,uj+1) pertence a , conforme desejado. QED Er

Mas e se também houver caminhos mais curtos (que )? Alguma dica / referência? k


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 .Tnkkntst

Todo puro em contém um caminho de comprimento . T n kkTnk

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 ):kkk

Pergunta 2: Se todo corte puro tiver bordas , o gráfico deve ter bordas ? M Ω ( k M )kMΩ(kM)

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(k1)m/2Kmk


EDIT 2: Agora eu fiz a pergunta 2 no mathoverflow .

Stasys
fonte

Respostas:

9

Resposta curta: não.

Seja um DAG completo (torneio transitivo) em n vértices com s e t sua fonte e afundar, e seja k = Gnst . Observe que pode haver no máximo quatro cortes disjuntos que contêm mais quen/3arestas incidentes emsou mais quen/3arestas incidentes emt. Portanto, se houver muitos cortes disjuntos, podemos assumir que existe um corteCque não contém um grande número de arestas incidentes emset.k=n/3n/3sn/3tCst

Agora vamos ser o subgráfico completo induzido em G pelo conjunto de vértices x tal que as bordas s x e x t não pertencem ao C . O número de vértices em X é pelo menos n / 3 , porque, caso contrário, C tocaria muitas arestas incidentes em s ou t . No entanto, X C não pode conter um caminho k , porque se esse caminho existisse, ele poderia ser concatenado com s e t para formar um caminho longo em GXGxsxxtCXn/3CstXCkst . Portanto, a camada de caminho mais longo de X C possui menos de k camadas e uma camada que contém mais de ( n / 3 ) / k = k vértices. Como essa é uma camada com a camada mais longa do caminho, ela é independente em X C e, portanto, completa em C , portanto C contém um caminho P através dos vértices dessa camada, de comprimento k . Esse caminho deve ser separado de todos os outros cortes.GCXCk(n/3)/k=kXCCCPk

Todo corte que não é deve conter a aresta de s até o início do caminho P ou a aresta do final do caminho P até t , caso contrário, não bloquearia o caminho s - P - t . Portanto, se C existir, pode haver no máximo três cortes disjuntos. E se C não existir (isto é, se todos os cortes cobrirem mais de n / 3 arestas incidentes em s ou em t ), poderá haver no máximo quatro cortes disjuntos. De qualquer forma, isso é muito menos que k cortes.CsPPtsPtCCn/3stk

David Eppstein
fonte
@ David: Argumento interessante (embora eu ainda não o tenha entendido: por que C deve ter um caminho k). Mas onde o argumento falha (deveria) se todos os caminhos st forem longos, de comprimento pelo menos k?
Stasys 17/01
11
@Stasys: G é um torneio, a prova usa esse fato, então é por isso que falharia.
Domotorp
@domotorp: obrigado, de fato, eu perdi a palavra "completo". Ainda não consigo encontrar uma falha, mas isso seria um fato contra-intuitivo: mesmo se houver muito caminho k em um torneio acíclico, não podemos selecionar muitos sistemas disjuntos de seus representantes (arestas).
Stasys 17/01
@ David: Na verdade, para ter as consequências mencionadas, podemos permitir que os cortes sejam apenas "quase disjuntos", ou seja, compartilhem arestas incidentes em s ou t (temos apenas 2 nessas arestas especiais). Um objetivo real é mostrar que G deve ter cerca de kN arestas, se soubermos que todo corte k "puro" (sem essas arestas especiais) deve ter N arestas. O seu argumento (muito bom, como agora vejo) pode ser modificado para essa situação ("quase desarticulada")?
Stasys 17/01
2
Se você permite que os cortes compartilhem arestas incidentes em s ou t, então por que você não pode fazer todos os cortes consistirem exatamente no conjunto de arestas incidentes em s? Por outro lado, meu argumento mostra que (com sua escolha de e k ) só pode haver um corte puro. Gk
David Eppstein