Existe um algoritmo para minimizar o conjunto de trabalho durante uma travessia topológica?

Question

Eu tenho um gráfico de dependência de tarefas, que forma um DAG.Estou à procura de um algoritmo para calcular a percorreção topológica ideal para minimizar o "conjunto de trabalho".Especificamente, defino o conjunto atual de trabalho como o conjunto de nós que foram visitados e que têm pelo menos uma borda de saída que é confinada.

Ainda mais útil seria um algoritmo para calcular a percursão topológica ideal que minimiza o número de despejos de cache, dado um cache de tamanho fixo para o conjunto de trabalho.

Existe um algoritmo para calcular esta travessia topológica?Eu posso fazer isso avidamente da ordem topológica, mas suspeito que é suboptimal.

Answer 1

Decidir se uma ordem topológica com o conjunto de trabalho de tamanho $ \ le k $ existe é np-completo, mesmo em gráficos bipartitários.

Podemos reduzir pathwidth Computação para este problema. Deixe $ g $ ser um gráfico não direcionado, cuja largura de caminho queremos calcular. Agora crie um gráfico direcionado $ h $ , com vértice $ v '$ para cada vértice $ v $ de $ g $ . Para cada borda $ (u, v) $ de $ g $ , crie uma vértice $ e _ {(u, v)} $ e dirigido bordas $ (v ', e _ {(u, v)}'), u ', e _ {(u, v)}') $ .

Agora considere uma ordem topológica de $ h $ . Defina a sequência correspondente de conjuntos de trabalho como $ x_1, \ lDOTs, x_p $ . Nós provamos que $ x_1, \ ldots, x_p $ é uma decomposição de caminho de $ g $ . Os conjuntos de trabalho incluem apenas vértices do tipo $ v '$ , porque os outros vértices não têm bordas de saída. Os conjuntos de trabalho por definição satisfazem a propriedade interseção $ i \ le j \ le k \ le j \ le k \ righttarrow x_i \ cap x_k \ subseteq x_j $ . Se houver uma borda $ (u, v) $ na $ g $ , então há bordas $ H $ de ambos $ v '$ e $ u '$ para $ e _ {(u, v)}' $ então deve haver um conjunto de trabalho $ X_i $ com $ v ', u' \ in x_i $ . Portanto, cada borda é um subconjunto de algum saco da decomposição do caminho e, portanto, $ x_1, \ lDOTs, x_p $ é uma decomposição de caminho de $ G $ .

Nós também podemos mostrar que qualquer caminho-decomposição de $ g $ corresponde a uma ordem topológica de $ H $ < / Span> (considere a ordem de eliminação do gráfico de intervalo subjacente). $ \ quadrado $

Para resultados positivos, gostaria de sugerir a olhar para algumas analogias de pathwidth para Dags na literatura. Com uma pesquisa rápida, encontrei as noções de largura de caminho dirigida e largura de Dag, mas parece que eles não são relevantes aqui, pois são triviais para Dags.