Contre-exemple d'algorithmes max-flow avec des poids irrationnels?

Il est connu que Ford-Fulkerson ou Edmonds-Karp avec l'heuristique fat pipe (deux algorithmes pour max-flow) ne doivent pas s'arrêter si certains des poids sont irrationnels. En fait, ils peuvent même converger vers la mauvaise valeur! Cependant, tous les exemples que j'ai pu trouver dans la littérature [références ci-dessous, plus les références qui y figurent] n'utilisent qu'une seule valeur irrationnelle: le nombre d'or conjugué , et d'autres valeurs qui sont soit rationnels, soit des multiples rationnels de . Ma principale question est:$\phi' = (\sqrt{5}-1)/2$$\phi'$

Question générale: que se passe-t-il avec les autres valeurs irrationnelles?

Par exemple (mais ne vous sentez pas obligé de répondre à toutes ces questions pour poster - je trouverais une réponse intéressante à n'importe laquelle ou à d'autres questions qui relèvent de la question générale ci-dessus):

1. Étant donné un , peut-on construire (ou même montrer l'existence de) ces contre-exemples?$\alpha \in \mathbb{R}$

2. Plus faiblement: existe-t-il des exemples connus qui utilisent une valeur irrationnelle essentiellement différente de ? Autrement dit, existe-t-il un qui n'est pas un multiple rationnel de (ou plus fortement pas dans ) et tel qu'il existe des contre-exemples pour Ford-Fulkerson et / ou Edmonds- Karp où tous les poids se trouvent dans ?$\phi'$$\alpha$$\phi'$$\mathbb{Q}(\phi')$$\mathbb{Q}(\alpha)$

3. Dans l'autre sens, existe-t-il un irrationnel tel que Ford-Fulkerson (resp., Edmonds-Karp) s'arrête avec la valeur correcte sur tous les graphiques dont les poids proviennent tous de ? (Ou plus fortement, à partir de Q ( α ) ?)$\alpha$$\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$$\mathbb{Q}(\alpha)$

Dans tous les cas, je veux supposer quelque chose comme le modèle réel de RAM, afin que des comparaisons arithmétiques et exactes exactes de nombres réels soient effectuées en temps constant.

(Il existe d'autres algorithmes de flux maximal qui sont connus pour fonctionner en temps fortement polynomial, même avec des poids réels arbitraires, ce qui explique peut-être pourquoi ce type de question n'a peut-être pas été approfondi. Mais après avoir simplement enseigné ces algorithmes dans ma classe d'algorithmes de premier cycle , Je suis toujours curieux à ce sujet.)

Références

• Un contre-exemple minimal pour Ford-Fulkerson a été donné par Zwick TCS 1999

• Un contre-exemple pour Edmonds-Karp a été donné par Queyranne ou Queyranne Math. Oper. Res. 1980 , même si je ne sais pas si celle-ci est minimale.

• Ceux-ci peuvent tous deux être trouvés dans les notes de cours de Jeff Erickson , le premier à la section 23.5 et le second à l'exercice 14 de la leçon 23.

La réponse est que pour chaque nombre irrationnel , il existe un réseau$r$

• $n=6$$m=8$
• dans laquelle sept arcs ont une capacité entière,
• $r$
• et sur lequel Ford-Fulkerson pourrait ne pas résilier.

Cela a été prouvé dans le document

Toshihiko Takahashi:
"Le réseau le plus simple et le plus petit sur lequel la procédure de flux maximal Ford-Fulkerson peut ne pas se terminer"
Journal of Information Processing 24, pp 390-394, 2016.
Lien: https: //www.jstage.jst.go. jp / article / ipsjjip / 24/2 / 24_390 / _article

Merci pour la question que j'ai trouvée pas vraiment naturelle mais tout de même assez amusante.

J'ai examiné la partie Ford-Ferkulson et je pense avoir trouvé un graphique qui est un contre-exemple et n'a qu'un seul bord avec une capacité irrationnelle α (le graphique peut fonctionner pour n'importe quel α).

Voici un PDF résumant ma tentative: https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (désolé c'est un peu laconique pour le moment mais n'hésitez pas à poser des questions)

Évidemment, le Ford-Felkurson nous laisse choisir le chemin d'augmentation comme nous le souhaitons ... Je ne suis pas sûr que ce serait possible pour Edmond-Karp.