Combien de coupes de bord disjointes un DAG doit avoir?

La question suivante est liée à l'optimalité de l' algorithme de programmation dynamique Bellman-Ford - plus court (voir cet article pour une connexion). En outre, une réponse positive impliquerait que la taille minimale d'un programme de branchement non déterministe monotone pour le problème STCONN est . $s$$t$$\Theta(n^3)$

Soit un DAG (graphe acyclique dirigé) avec un nœud source et un nœud cible . A - coupe est un ensemble d'arêtes, dont la suppression détruit toutes - chemins de longueur ; nous supposons qu'il existe des chemins dans . Notez que les chemins - courts n'ont pas besoin d' être détruits.$G$$s$$t$$k$$s$$t$$\geq k$$G$$s$$t$

Question: Est - ce que doit avoir au moins (environ) coupes disjointes ? $G$$k$ $k$

S'il n'y a pas de - chemins plus courts que , la réponse est OUI, car nous avons le fait min-max connu suivant (un double du théorème de Menger ) attribué à Robacker . Une coupe - est une coupe pour (détruit tous chemins - ).$s$$t$$k$^$\ast$t k k = 1 s $s$$t$$k$$k=1$ $s$$t$

Réalité: dans tout graphique dirigé, le nombre maximal de coupes - disjointes sur les bords est égal à la longueur minimale d'un chemin - . t s $s$$t$$s$$t$

Notez que cela vaut même si le graphique n'est pas acyclique.

Preuve: Trivialement, le minimum est au moins le maximum, car chaque chemin - coupe chaque coupe - dans un bord. Pour voir l'égalité, soit la longueur du chemin le plus court de à . Soit , pour , et soit l'ensemble des arêtes quittant . Il est clair que les ensembles sont disjoints, car les ensembles sont. Il reste donc à montrer que chaque est un -t s t d ( u ) s u U r = { u : d ( u ) = r } r = 1 , … , d ( t ) E r U r E r U r E r s t s t p = ( u 1 , u 2 , … , u m$s$$t$$s$$t$$d(u)$$s$$u$$U_r=\{u\colon d(u)=r\}$$r = 1,\ldots, d(t)$$E_r$$U_r$$E_r$$U_r$$E_r$$s$$t$Couper. Pour le montrer, prenez un chemin - arbitraire avec et . Puisque , la séquence des distances doit atteindre la valeur en commençant à et en augmentant la valeur d'au plus à chaque étape. Si une valeur est diminuée, alors nous devons atteindre la valeur cette dernière. Donc, il doit y avoir un où un saut de à se produit, signifiant le bord$s$$t$$p=(u_1, u_2, \ldots,u_m)$u m = t d ( u i + 1 ) ≤ d ( u i ) + 1 d ( u 1 ) , … , d ( u m ) d ( u m ) = d ( t ) d ( u 1 ) = d ( s ) = 0 1 d $u_1=s$$u_m=t$$d(u_{i+1})\leq d(u_i)+1$$d(u_1),\ldots,d(u_m)$$d(u_m)=d(t)$$d(u_1)=d(s)=0$$1$d ( u i ) j d ( u j ) = r d ( u j + 1 ) = r + 1 ( u j , u j + 1 ) E $d(u_i)$$d(u_i)$$j$$d(u_j)=r$$d(u_{j+1})=r+1$$(u_j,u_{j+1})$ appartient à , comme souhaité. QED $E_r$

Mais que se passe-t-il s'il existe également des chemins plus courts (que )? Un indice / référence? $k$

---

$^{\ast}$ JT Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, Research Memorandum RM-1660, The RAND Corporation, Santa Monica, Californie, [12 janvier] 1956.

---

EDIT (un jour plus tard): Via une courte et très belle argumentation, David Eppstein répondu à la question ci - dessus d' origine négative : la complète DAG (un tournoi transitif ) ne peut pas avoir plus de quatre disjoints -cuts! En fait, il prouve le fait structurel intéressant suivant , pour about . Une coupe est pure si elle ne contient pas d'arêtes incidentes à ou à . k k $T_n$$k$$k$ s$\sqrt{n}$$s$$t$

Chaque pure dans contient un chemin de longueur . T n$k$$T_n$$k$

Cela implique en particulier que tous les deux coupures pures doivent se croiser! Mais il y a peut-être encore beaucoup de coupes pures qui ne se chevauchent pas «trop». D'où une question détendue (les conséquences pour STCONN seraient les mêmes ):$k$$k$

Question 2: Si chaque coupe pure a des bords , le graphique doit-il avoir environ des bords ? ≥ M Ω ( k ⋅ M $k$$\geq M$$\Omega(k\cdot M)$

Le lien avec la complexité de STCONN vient du résultat d'Erdős et Gallai qu'il faut supprimer tous les bords ( sauf de (non dirigé) afin de détruire tous les chemins de longueur . K m$(k-1)m/2$$K_m$$k$

---

EDIT 2: J'ai maintenant posé la question 2 à mathoverflow .

Réponse courte: non.

Soit un DAG complet (tournoi transitif) sur sommets avec et sa source et son puits, et soit . Observez qu'il peut y avoir au plus quatre coupes disjointes contenant plus de tham arêtes incidentes à ou plus de arêtes incidentes à . Donc, s'il doit y avoir de nombreuses coupes disjointes, nous pouvons supposer qu'il existe une coupe qui ne contient pas un grand nombre d'arêtes incidentes à et .n s t k = $G$$n$$s$$t$ n/3sn/3tCs$k=\sqrt{n/3}$$n/3$$s$$n/3$$t$$C$$s$$t$

Maintenant , nous le sous - graphe complet induit dans par l'ensemble des sommets tels que les bords et ne appartiennent à . Le nombre de sommets dans est au moins , car sinon toucherait trop d'arêtes incidentes à ou . Cependant, ne peut pas contenir un -path, parce que si un tel chemin existait , il pourrait être concaténée avec et pour former un long chemin dans . Par conséquent, la superposition le plus long chemin deG x s x x t C X n / 3 C s t X ∖ C k s t G ∖ C X ∖ C k ( n / 3 ) / k = k X ∖ C C C P $X$$G$$x$$sx$$xt$$C$$X$$n/3$$C$$s$$t$$X\setminus C$$k$$s$$t$$G\setminus C$$X\setminus C$ a moins de couches, et a une couche contenant plus de sommets. Comme il s'agit d'une couche de la couche de chemin la plus longue, elle est indépendante dans , et donc complète en , donc contient un chemin travers les sommets de cette couche, de longueur . Cette voie doit être disjointe de toutes les autres coupes.$k$$(n/3)/k=k$$X\setminus C$$C$$C$$P$$k$

Chaque coupe qui n'est pas doit contenir soit l'arête de jusqu'au début du chemin soit l'arête de la fin du chemin vers , sinon elle ne bloquerait pas le chemin - - . Donc, si existe, il peut y avoir au plus trois coupes disjointes. Et si n'existe pas (c'est-à-dire si toutes les coupes couvrent plus de bords incidents à ou à ) il peut y avoir au plus quatre coupes disjointes. Quoi qu'il en soit, c'est beaucoup moins que coupures.s P P t s P t C C n / 3 s t $C$$s$$P$$P$$t$$s$$P$$t$$C$$C$$n/3$$s$$t$$k$