Algoritmo exato para problemas de identificação de bordas no DAG

Estou implementando uma parte do sistema que requer alguma ajuda. Portanto, estou enquadrando-o como um problema gráfico para torná-lo independente de domínio.

Problema: Recebemos o gráfico acíclico . Sem perda de generalidade, assuma que tem exatamente um vértice de origem e exatamente um vértice de afundamento ; deixar denotam o conjunto de todos os caminhos dirigidos de a em . Também é dado um conjunto de vértices . O problema é atribuir pesos inteiros não negativos às arestas de , para que dois caminhos em tenham o mesmo peso se e somente se eles contiverem o mesmo subconjunto de vértices em $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ $R$ . (O peso de um caminho é a soma dos pesos de suas arestas.) O intervalo de pesos dos caminhos em deve ser o menor possível. $P$

Atualmente, minha abordagem não parece eficiente; Estou apenas procurando algumas referências à literatura ou algumas boas idéias. Qualquer outra coisa também é apreciada.

Edit: Existe uma prova de dureza para este problema? A numeração compacta sempre existe?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph user5153
fonte

esclareça "O intervalo de pesos dos caminhos em P deve ser ideal". Os pesos são apenas números inteiros? São permitidos pesos negativos? Ótimo significa "o menor alcance possível" ou significa outra coisa?

Artem Kaznatcheev

Eu editei a pergunta. Obrigado por seu comentário. os pesos devem ser números inteiros não negativos e o intervalo deve ser o menor possível.

precisa saber é o seguinte

Uma estratégia simples para chegar a uma solução válida seria atribuir uma potência diferente de dois para cada vértice v em R, usar esse número como o peso de todas as arestas recebidas para ve atribuir peso zero a todas as arestas restantes. Obviamente, isso pode não ser o ideal, mas pelo menos fornece um limite superior no intervalo necessário. É sempre uma melhoria fazer com que pesos diferentes através do mesmo vértice em R tenham pesos diferentes um do outro, ou você pode simplificar o problema fazendo com que os pesos correspondam aos vértices e não às arestas?

David Eppstein

A resposta do BTW @ DavidEppstein mostra que o peso total máximo de um caminho é

. Isso é apertado para constantes. Como exemplo, você pode pegar o gráfico

O (2^{| R |})

$O(2^{|R|})$

G = (V, E)

$G = (V, E)$

V = [n] \cup {s, t}

$V = [n] \cup \{s, t\}$

. Deixe também

. Existem

caminhos diferentes em

e, como cada caminho possui um peso inteiro não negativo, pelo menos um precisa ter um peso de pelo menos

E = {(i, j) : i < j} \cup {(s, 1), (n, t), (s, t)}

$E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$

R = [n]

$R = [n]$

2^{n}

$2^n$

R

$R$

2^{n} - 1

$2^n -1$

Sasho Nikolov 07/02

Claro, eu quis dizer apertado no pior dos casos (na verdade, escrevi isso na primeira versão deste comentário que se perdeu). pensei que seria bom primeiro estabelecer alguns limites absolutos, já que ninguém abordou o problema de otimização ainda.

Sasho Nikolov

nunca ouvi falar desse problema exatamente na literatura [talvez alguém o tenha] no entanto, como um "problema próximo", parece-me que a árvore de abrangência mínima teria propriedades úteis para resolver seu problema. por exemplo, talvez gerar duas árvores abrangentes mínimas, começando pelo vértice de origem e pelo vértice de sincronização e propagá-las para fora até tocarem, etc., possa resolver o problema ou dar uma resposta próxima. antes que alguém me fale sobre isso aqui, por favor, entenda que estou estendendo a idéia do MST para ser gerada a partir de um determinado vértice [normalmente ele começa na borda mais curta de todo o gráfico]. se não funcionar, ficaria curioso pelo motivo.

vzn
fonte

Desculpe, mas não vejo a relevância desta resposta para esta pergunta.

David Eppstein

talvez você tenha uma idéia melhor do que ele está falando? faz sentido para você como indicado?

vzn

Ele precisa atribuir pesos às arestas. Como o cálculo de um MST ajudaria isso?

Nicholas Mancuso

ok em lê-lo, e com mais ninguém propondo uma resposta, parecia que o problema poderia ser convertido em duas partes-- (1) atribuir pesos com base em critérios / restrições, (2) encontrar caminhos mais curtos com base nesses pesos. parece que o MST poderia ser útil em (2). ou talvez não! (por exemplo, talvez 1/2 estão fortemente acoplados)

vzn

Não. As árvores abrangentes mínimas são apenas para gráficos não direcionados; o gráfico de entrada é direcionado. Além disso, as árvores de abrangência mínima são apenas superficialmente relacionadas aos caminhos mais curtos.

Jeffε

Algoritmo exato para problemas de identificação de bordas no DAG

Respostas: