Podando um dígrafo fortemente conectado

10

Dado um dígrafo fortemente conectado G com arestas ponderadas, eu gostaria de identificar arestas que provavelmente não fazem parte de nenhum subgrafo mínimo fortemente conectado (MSCS) de G.

Um método para encontrar essas arestas é um algoritmo de Floyd-Warshall modificado. Usando o algoritmo de Floyd-Warshall, é possível identificar quais arestas nunca são a melhor opção para ir do vértice i para j. Esses nós não podem fazer parte de um MSCS porque é melhor substituí-los por duas ou mais outras arestas.

A técnica de poda de Floyd-Warshall funciona muito bem quando os pesos das arestas variam significativamente, mas muito pouco quando os pesos das arestas são semelhantes, mas de magnitude grande.

Você conhece algum método de poda eficaz para pesos de borda grandes e semelhantes? Esse problema é equivalente a um problema mais comum que eu não reconheço? Esse tipo de poda já foi estudado anteriormente na literatura?

Nate
fonte
11
Não consigo responder a essa pergunta sem ler a literatura sobre o problema. Você já tentou ler a literatura? Você pode resumir o que encontrou?
Warren Schudy
11
Grande parte da literatura está preocupada em encontrar algoritmos de aproximação, alguns dos quais são bastante bons. A maioria deles opera por meio de contração do ciclo, com bons resultados. Estou tendo problemas para encontrar literatura para poda em vez de aproximação, e é por isso que me pergunto se o problema da poda é uma generalização de um problema mais comum que eu posso ler. Qualquer dica sobre a literatura relacionada é bem-vinda.
Nate
11
Que função está sendo aproximada pelos algoritmos de aproximação e como isso difere da poda?
Suresh Venkat
As aproximações estão aproximando o subgráfico mínimo fortemente conectado. Como eu disse, eles costumam usar a contração do ciclo para fazer isso. A poda por meio da contração do ciclo pode resultar em um subgráfico não ideal (portanto, aproximação). Quero podar para garantir que não tenha podado nenhuma aresta que apareça no MSCS.
Nate

Respostas:

3

Assumimos que os pesos das arestas são números inteiros positivos. Dado um grafo orientado G com pesos das arestas, chamar uma aresta e redundante se e não pertence a qualquer mínimo de peso fortemente ligado que abrange subgráficos de L .

Afirmamos que, a menos que P = NP, não haja algoritmo de tempo polinomial que sempre encontre uma aresta redundante em um determinado gráfico direcionado com pesos de aresta, desde que exista um. Mais precisamente:

Teorema . Dado um gráfico direcionado G com pesos de arestas, é NP difícil encontrar uma aresta redundante em G ou declarar que G não possui uma aresta redundante.

Prova . A principal observação é que, se G tiver um subgrafo de abrangência fortemente unido, com peso mínimo e exclusivo , você poderá calcular esse subgrafo removendo as arestas redundantes uma a uma. Portanto, resta mostrar que a singularidade não facilita o problema do subgrafo de extensão fortemente conectado com peso mínimo, mas isso é comprovado no próximo lema. QED .

Lema . Dado um gráfico direcionado G com pesos das arestas, é NP difícil calcular o peso do subgrafo de extensão de peso mínimo fortemente conectado de G, mesmo com a promessa de que G tem um subgrafo de extensão de peso mínimo exclusivo e fortemente conectado.

Prova . Como você sabe , o problema sem a promessa é NP-difícil (mesmo para o caso de peso unitário) devido a uma redução do problema do circuito Hamiltoniano. Reduzimos o problema sem a promessa ao problema com a promessa.

Seja G um gráfico direcionado com pesos das arestas. Rotular os bordos de G por e 0 , e 1 , ..., e m -1 , onde m é o número de extremidades em L . Deixe w i ser determinado o peso da aresta de um e i . Seja o novo peso wi = 2 m w i +2 i . Então é fácil verificar se G com os novos pesos possui um subgrafo de abrangência fortemente unido, com peso mínimo. Também é fácil verificar se o peso mínimoW de um subgráfico de extensão fortemente conectado em G com os pesos originais pode ser calculado a partir do peso mínimo W ′ em G com os novos pesos como W = ⌊ W ′ / 2 m ⌋. QED .

Tsuyoshi Ito
fonte
2
Sim, obviamente, é NP difícil encontrar todas essas arestas. Não estou procurando todas essas arestas, estou procurando um conjunto de arestas que você possa determinar que podem ser removidas em tempo polinomial. O algoritmo de Floyd-Warshall pode ser usado para encontrar um desses conjuntos de arestas, conforme descrito acima. Fiquei me perguntando se existem outras maneiras de identificar um subconjunto das bordas removíveis em tempo polinomial.
Nate