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 T
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 ′
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?
graph-theory
graph-algorithms
Martin Vatshelle
fonte
fonte
Respostas:
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 ′D′ D v G D v D′ v D′
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 ′ GD′ G D′ G
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.
fonte