Ordre topologique positif, prendre 2

12

Ceci fait suite à la récente question de David Eppstein et est motivé par les mêmes problèmes.

Supposons que j'ai un point avec des poids réels sur ses sommets. Initialement, tous les sommets ne sont pas marqués. Je peux changer l'ensemble des sommets marqués soit (1) en marquant un sommet sans prédécesseurs non marqués, soit (2) en démarquant un sommet sans successeurs marqués. (Ainsi, l'ensemble des sommets marqués est toujours un préfixe de l'ordre partiel.) Je veux trouver une séquence d'opérations de marquage / démarcation qui se termine par tous les sommets marqués, de sorte que le poids total des sommets marqués soit toujours non négatif .

  • Est-il difficile de trouver une telle séquence d'opérations? Contrairement au problème de David , il n'est même pas clair que ce problème soit dans NP; en principe (bien que je n'ai pas d'exemples) chaque séquence de mouvement légale pourrait avoir une longueur exponentielle. Le mieux que je puisse prouver, c'est que le problème est dans PSPACE.

  • L'opération de démarquage est-elle réellement inutile? S'il existe une séquence de déplacement valide, doit-il y avoir une séquence de déplacement valide qui ne marque jamais un sommet? Une réponse affirmative rendrait ce problème identique à celui de David . D'un autre côté, si la suppression du marquage est parfois nécessaire, il devrait y avoir un petit exemple (taille constante) qui le prouve.

Jeffε
la source
1
Cet article montre qu'un problème vaguement lié est difficile pour PSPACE: arxiv.org/abs/1009.3217
Jeffε
Cela ressemble beaucoup à un jeu de galets: en.wikipedia.org/wiki/Pebble_game .
Warren Schudy
Un article récent sur le caillou: cs.utoronto.ca/~philipp/pages/papers/BWPebbling.pdf . Le jeu de galets noirs est similaire au vôtre mais différent en ce que les nœuds intermédiaires peuvent être non marqués même si un successeur est marqué.
Warren Schudy

Réponses:

5

Lors de notre séminaire de recherche régulier 666, nous avons fourni la preuve suivante.

Nous commençons avec quelques définitions. Soit P notre poset. Par souci de simplicité, supposons qu'aucun des poids ne soit égal à zéro. Notons le poids d'un sommet par w (x) et la somme des poids d'un ensemble par w (X). Nous disons qu'un ensemble X est Y-up (fermé) s'il est contenu dans Y et que chaque élément de Y qui est plus grand qu'un élément de X est également dans X. De même, disons qu'un ensemble X est Y-down s'il est contenu dans Y et chaque élément de Y qui est plus petit qu'un élément de X est également dans X. Dans ce langage, l'ensemble des éléments marqués doit toujours être P-down.

Nous prouvons par contradiction. Prenez la séquence de marquage / retrait la plus courte qui marque chaque élément. Nous appelons ces séquences complètes. À un moment donné, considérez l'ensemble des éléments qui ont été marqués auparavant mais qui ne le sont plus. Notons cet ensemble par U.

Revendication: w (U)> 0.

Preuve: Nous prouvons que le poids de tout ensemble U-up, X, est positif. La preuve est par induction sur la taille de X. S'il y a un ensemble X-down, Y, tel que w (Y)> 0, alors que par induction on sait que w (X \ Y)> 0 (puisqu'il est X-up), nous avons également w (X)> 0. Si pour chaque ensemble X-down, Y, nous avons w (Y) <0, alors en supprimant jusqu'à ce point tous les marquages ​​et annotations des éléments de X de notre séquence, nous obtenons une séquence complète plus courte. Nous avons terminé avec la preuve de la réclamation.

Supposons maintenant que nous ayons une séquence complète où w (U)> 0 à tout moment pour l'ensemble U d'éléments actuellement non marqués. Prenez la séquence que nous obtenons à partir de cela en prenant le premier marquage de chaque élément et en ne démarquant jamais rien. Il est clair que ce sera également une séquence complète satisfaisant que l'ensemble des éléments marqués est toujours P-down. De plus, la somme des poids sera toujours au moins autant que dans la séquence d'origine car à tout moment la différence est w (U). Nous avons fini.

Avec cette méthode, on peut même prouver que si au lieu de marquer l'ensemble de P, nous voulons seulement marquer un sous-ensemble de P, alors cela peut être fait avec une séquence de marquages ​​suivie d'une séquence de non marquages. La preuve est la même sauf qu'à la fin certains éléments, U, restent non marqués mais ceux-ci peuvent être déplacés à la fin de la séquence car le poids de tout ensemble U-up est positif.

domotorp
la source
1
Vos définitions de Y-up et Y-down sont identiques. Vraisemblablement, un sous-ensemble X de Y est Y-bas si chaque élément de Y qui est plus petit qu'un élément de X est également dans X.
Jeffε
1
Très cool! La réponse pourrait être plus claire si la première ligne indiquait quelle affirmation vous étiez en train de prouver. Je suppose que c'est une preuve que le démarquage n'est jamais nécessaire (si vous pouvez le résoudre en utilisant le démarquage, vous pouvez trouver une séquence qui le résout également sans jamais démarquer quoi que ce soit)? (Et non, par exemple, une preuve que ce problème est NP-dur / PSPACE-dur, ou d'un algorithme à temps polynomial qui peut décider si une telle séquence de marquage existe (ou la trouver).) Aussi, plus loin dans l'exposition où il dit "à tout moment", je ne sais pas si cela signifie "à tout moment" ou "à un moment donné"; Je suppose que tu veux dire l'ancien?
DW