Digrafo equivalente mínimo em relação às fontes e sumidouros

11

Dado um DAG (dirigido gráfico acíclico) , com fontes e pias . Encontre um DAG , com as fontes e os dissipadores , com número mínimo de arestas, de modo que:S T D S TDSTDST

Para todos os pares existe um caminho de para em se e somente se houver um caminho de para em .u v D u v D uS,vTuvDuvD

Uma aplicação disso é representar uma família definida por um DAG. Para tal representação, cada fonte é uma variável no universo e cada coletor é um conjunto na família de conjuntos, e um elemento u está em um conjunto S se e somente se houver um caminho do vértice representando u para o vértice representando o defina S.

Esse problema é bem conhecido? Existe um algoritmo polinomial para esse problema?

Martin Vatshelle
fonte
Eu acho que a solução deve ser um subgrafo do gráfico original, certo? Se sim, acho que esse problema captura a tampa do conjunto, através da redução padrão que mostra que a árvore do Steiner Steiner é difícil: crie um vértice para cada elemento, um vértice para cada conjunto e uma aresta direcionada (S, u) se o conjunto S contém o elemento u. Em seguida, adicione um novo vértice e arestas a todos os vértices definidos. Existe um caminho desse novo vértice para todos os sumidouros (o elemento vértices). Para preservar todos eles, precisamos selecionar o número mínimo de vértices definidos que cubram todos os elementos.
Michael Lampis
Não, em geral, eu diria que não deve ser um subgrafo do gráfico original. As origens são elementos e você precisa do elemento se e somente se algum conjunto contiver esse elemento. Os coletores são conjuntos e você não pode excluir os conjuntos que você deve representar, portanto, a única coisa que se pode fazer se começar a partir do gráfico ingênuo em que todos os nós são coletores ou fontes é adicionar vértices e mover / excluir arestas.
Martin Vatshelle
O problema ainda não parece bem definido. Quais são as restrições no conjunto de vértices de ? Você precisa que o conjunto de vértices de seja o mesmo que o conjunto de vértices de ? Que as fontes e sumidouros de são as mesmas que as fontes e sumidouros de ? Que existe uma função mapeando um vértice de para um vértice de , e a condição é realmente que existe um caminho de para em se houver um caminho de a emD D D D f : V DV D D D u v D f ( u ) f ( v ) D DDDDDf:VDVDDDuvDf(u)f(v)D? Cada um pode levar a um problema ligeiramente diferente. Edite a pergunta para esclarecer?
DW
Esclarei a questão, na verdade quero dizer que as fontes e sumidouros são os mesmos. Eu acho que o mapeamento está bem próximo do mesmo, a única maneira de mapear dois sumidouros para o mesmo nó é se eles puderem ser acessados ​​pelo mesmo conjunto de fontes, ou seja, representa o mesmo conjunto. A única maneira de mapear duas fontes para o mesmo nó é se elas atingirem exatamente os mesmos coletores. Então, acho que depois de um simples pré-processamento de D os problemas seriam equivalentes.
Martin Vatshelle 28/08/2015
O dag D é realmente irrelevante para o problema, não é? Você também pode pegar um gráfico bipartido entre S e T como entrada.
Emil Jeřábek 3.0 de

Respostas:

1

Vamos supor que contenha apenas fontes e sumidouros, já que a entrada pode ser convertida em uma entrada equivalente facilmente.D

Em seguida, observe que, em qualquer solução para , cada vértice corresponde a uma biclique no gráfico não direcionado subjacente de (a biclique entre todas as fontes que atingem em e todos os sumidouros alcançados de em ). D v G D v D v D DDvGDvDvD

Conjeturo que, se é óptima, em seguida, ela contém um vértice de corte que 1: 1 corresponde a uma óptima cobertura biclique de . Então, qualquer mínimo vértice de corte em corresponde a uma óptima cobertura biclique em . No entanto, como a BICLIQUE COVER (também conhecida como BIPARTITE DIMENSION) é NP-completa, é improvável que seu problema admita um algoritmo de tempo polinomial, a menos que minha conjectura falhe. G D GDGDG

Observe que, mesmo que minha conjectura seja válida, tecnicamente esse argumento não prova a dureza NP do seu problema, pois a redução não é uma redução de Karp, mas de Cook.

igel
fonte