Problema mínimo de cobertura de caminho

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á- ser um gráfico contendo $k$ $Z_k$ vértices. Marcamos cada vértice com um parmodo que. A seguir, nomeamos vértices usando seu rótulo. O conjunto de arestas emé definido da seguinte forma: . $\frac{k(k+1)}{2}$ $(i,j)$ $1 \leq i \leq j \leq k$ $Z_k$ $\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$

Qual é a cobertura mínima do caminho de ? $Z_k$

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 $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ . $\frac{k^2}{4}-\frac{k}{2}$

Atenciosamente,

Pierre

graph-theory co.combinatorics application-of-theory Pierre
fonte

deveria ser

vez de

na definição de uma aresta de

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Suresh Venkat

Respostas:

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