Problema mínimo de cobertura de caminho

10

Estamos trabalhando em computadores distribuídos e descobrimos um problema de complexidade que reduz a um caminho mínimo que cobre o problema. Atualmente, não sabemos como resolvê-lo. O problema é o seguinte:

Vamos ser algum número inteiro, e deixá- Z k ser um gráfico contendo k ( k + 1 )kZk vértices. Marcamos cada vértice com um par(i,j), demodo que1ijk. A seguir, nomeamos vértices usando seu rótulo. O conjunto de arestas emZké definido da seguinte forma: {((i,j),(i,j))| i>iji}.k(k+1 1)2(Eu,j)1 1EujkZk{((Eu,j),(Eu,j))|Eu>EujEu}

Qual é a cobertura mínima do caminho de ?Zk

Lendo "Problemas de cobertura de caminho em dígrafos e aplicativos para testar programas" por Ntafos et al. , vimos que a cobertura mínima do caminho é igual ao cardeal do maior conjunto incomparável de vértices. Estávamos pensando no seguinte conjunto: que tem um cardeal de k 2S={(Eu,j):Euk/2j<k/2} .k24-k2

Atenciosamente,

Pierre

Pierre
fonte
deveria ser vez de j i na definição de uma aresta de Z k ? jjjEuZk
Suresh Venkat

Respostas:

10

Parece que seu gráfico é um DAG fechado transitivamente, certo? Em caso afirmativo (e isso provavelmente é uma reafirmação do que você diz em sua citação de Ntafos et al), o número mínimo de caminhos necessários para cobrir o DAG é apenas o número máximo de elementos incomparáveis ​​em pares; esse é o teorema de Dilworth .

Seu exemplo pode ser simples o suficiente para identificar diretamente esse conjunto incomparável máximo, mas, em geral, é possível encontrá-lo em tempo polinomial, por um algoritmo baseado na correspondência de gráficos. A seção "Prova através do teorema de König" do artigo da Wikipedia sobre o teorema de Dilworth explica como.

David Eppstein
fonte