Élagage d'un digraphe fortement connecté

Étant donné un digraphe G fortement connecté avec des bords pondérés, je voudrais identifier des bords qui ne font manifestement pas partie d'un sous-graphique minimal fortement connecté (MSCS) de G.

Une méthode pour trouver de tels bords est un algorithme de Floyd-Warshall modifié. En utilisant l'algorithme Floyd-Warshall, on peut identifier quelles arêtes ne sont jamais la meilleure option pour passer du sommet i à j. Ces nœuds ne peuvent pas faire partie d'un MSCS car il est préférable de les remplacer par deux ou plusieurs autres arêtes.

La technique d'élagage Floyd-Warshall fonctionne assez bien lorsque les poids des bords varient considérablement, mais très mal lorsque les poids des bords sont similaires mais de grande ampleur.

Connaissez-vous des méthodes d'élagage efficaces pour des poids de bord importants et similaires? Ce problème est-il équivalent à un problème plus courant que je ne reconnais pas? Ce type d'élagage a-t-il été étudié auparavant dans la littérature?

ds.algorithms graph-theory graph-algorithms Nate
la source

Je ne peux pas répondre à cette question sans lire la littérature sur le problème. Avez-vous essayé de lire la littérature vous-même? Pouvez-vous résumer ce que vous avez trouvé?

Warren Schudy

Une grande partie de la littérature concerne la recherche d'algorithmes d'approximation, dont certains sont assez bons. La majorité d'entre eux opèrent par contraction du cycle, avec de bons résultats. J'ai du mal à trouver de la littérature pour l'élagage au lieu de l'approximation, c'est pourquoi je me demande si le problème de l'élagage est une généralisation d'un problème plus courant que je peux lire. Tous les conseils sur la littérature sont les bienvenus.

Nate

Quelle fonction est approximée par les algorithmes d'approximation et en quoi cela diffère-t-il de l'élagage?

Suresh Venkat

Les approximations sont approximatives du sous-graphique minimal fortement connecté. Comme je l'ai dit, ils utilisent souvent la contraction du cycle pour ce faire. L'élagage via la contraction du cycle peut entraîner un sous-graphique non optimal (d'où une approximation). Je veux tailler de telle sorte que je puisse garantir que je n'ai pas taillé les bords qui apparaissent sur le MSCS.

Nate

Réponses:

Nous supposons que les poids de bord sont des entiers positifs. Étant donné un graphe orienté G avec des poids de bord, appeler un bord e redondant si e ne fait partie l'une à liaison forte minimum de poids de sous - graphes couvrant G .

Nous affirmons qu'à moins que P = NP, il n'y a pas d'algorithme à temps polynomial qui trouve toujours un bord redondant dans un graphique dirigé donné avec des poids de bord tant qu'il y en a un. Plus précisément:

Théorème . Étant donné un graphe orienté G avec des poids de bord, il est NP-difficile de trouver un bord redondant dans G ou de déclarer que G n'a pas de bord redondant.

Preuve . L'observation clé est que si G a un sous-graphe s'étendant fortement connecté de poids minimum unique , alors vous pouvez calculer ce sous-graphe en supprimant les bords redondants un par un. Par conséquent, il reste à montrer que l'unicité ne facilite pas le problème de sous-graphe couvrant fortement lié au poids minimum, mais cela est prouvé par le lemme suivant. QED .

Lemme . Étant donné un graphe orienté G avec des poids de bord, il est NP-difficile de calculer le poids du sous-graphe couvrant fortement connecté de poids minimum de G, même sous la promesse que G a un sous-graphe s'étendant fortement connecté de poids minimum unique.

Preuve . Comme vous le savez , le problème sans la promesse est NP-difficile (même pour le cas du poids unitaire) par une réduction du problème du circuit hamiltonien. Nous réduisons le problème sans la promesse au problème avec la promesse.

Soit G un graphe orienté avec des poids de bord. Attribuer les bords de G par e ₀ , e ₁ , ..., e _{m -1} , où m est le nombre d'arêtes dans G . Soit w _i le poids donné du bord e _i . Soit le nouveau poids w ′ _i = 2 ^m w _i +2 ⁱ . Il est ensuite facile de vérifier que G avec les nouveaux poids possède un sous-graphe couvrant fortement connecté unique. Il est également facile de vérifier que le poids minimumW d'un sous-graphe couvrant fortement connecté en G avec les poids originaux peut être calculé à partir du poids minimum W ′ en G avec les nouveaux poids comme W = ⌊ W ′ / 2 ^m ⌋. QED .

Tsuyoshi Ito
la source

Oui, évidemment, il est difficile de trouver tous ces bords NP. Je ne cherche pas toutes ces arêtes, je cherche un ensemble d'arêtes dont vous pouvez déterminer qu'elles sont élaguables en temps polynomial. L'algorithme Floyd-Warshall peut être utilisé pour trouver un tel ensemble d'arêtes, comme décrit ci-dessus. Je me demandais s'il y avait d'autres façons d'identifier un sous-ensemble des bords amovibles en temps polynomial.

Nate