Verallgemeinerung des Dilworth-Theorems für markierte DAGs

11

Eine Antichain in einer DAG ist eine Teilmenge A V von Scheitelpunkten, die paarweise nicht erreichbar sind, dh es gibt kein v v 'A, so dass v von v ' in E erreichbar ist . Aus dem Dilworth-Theorem in der Teilordnungstheorie ist bekannt, dass DAG, wenn es keine Antichain der Größe k N hat , in einer Vereinigung von höchstens k - 1 disjunkten Ketten, dh gerichteten Pfaden , zerlegt werden kann .(V,E)AVvvAvvEkNk1

vλ(v)ΣAVΣAminaΣ|{vAλ(v)=a}| kNWas kann ich über seine Struktur annehmen? Kann ich es auf besondere Weise zersetzen? Der Fall von verwirrt mich bereits , interessiert mich aber auch für den Fall eines allgemeinen endlichen Etikettensatzes.Σ={a,b}

Um dies für zu visualisieren , bedeutet die Aussage, dass keine Antichain der markierten Größe , dass es keine Antichain gibt, die mindestens mit Eckpunkte und mit bezeichnete Eckpunkte enthält ; Es kann beliebig große Antichains geben, sie müssen jedoch nur Elemente oder nur Elemente enthalten, höchstens bis zu Ausnahmen. Es scheint, dass das Nichtzulassen großer Antichains erzwingen sollte, dass die DAG im Wesentlichen zwischen Teilen mit großer Breite für markierte Eckpunkte und großer Breite für "wechselt"Σ={a,b}Gkkakbabk1ab-beschriftete Eckpunkte, aber ich konnte diese Intuition nicht formalisieren. (Natürlich muss eine geeignete strukturelle Charakterisierung zusätzlich zur Form der DAG über die Beschriftungen von Eckpunkten sprechen, da bereits für und auf die Bedingung von völlig willkürlichen DAGs erfüllt wird, wann immer alle Eckpunkte tragen das gleiche Etikett.)k1{a,b}

a3nm
quelle
1
@Saeed, Nein das funktioniert nicht. Ihre Verwirrung ergibt sich aus der Tatsache, dass wenn ein Buchstabe nicht in einer Antichain erscheint, seine beschriftete Größe . Nehmen wir zum Beispiel einen vollständigen zweigliedrigen Graphen G = (A, B, E), wobei jede Kante von A nach B ausgerichtet ist. Beschriften Sie jeden Scheitelpunkt von A mit und jeden Scheitelpunkt von B mit . Dann hat jede Antichain höchstens eine Farbe und hat daher die Größe , aber Sie können sie nicht mit disjunkten Ketten bedecken . Gleiche mit einem DAG , dass Sie mit dem Etikett nur. 0ab0m(k1)a
Holf
@holf, richtig, ich dachte, wir zählen über Etiketten, wo sie in der Antichain erscheinen. Ich habe nicht bemerkt, dass min über alle Elemente von Sigma geht. Ich denke, es ist eine etwas seltsame Definition.
Saeed
@Saeed: Es geht darum, Antichains mit einer Vielzahl von Symbolen zu verbieten. Die Intuition dafür ist, dass wir die Komplexität eines Problems auf DAGs untersuchen, die trivial wird, wenn Sie so große Antichains haben (ausreichend viele Vorkommen unvergleichlicher Symbole). Um die allgemeine Traktierbarkeit zu zeigen, müssen wir nur den Fall von DAGs behandeln, bei denen dieses Muster nicht auftritt. Daher möchten wir herausfinden, wie solche DAGs zerlegt werden können, um einen traktierbaren Algorithmus für sie zu entwerfen. (Im unbeschrifteten Fall führt beispielsweise die
Kettenzerlegung

Antworten:

7

Mit Charles Paperman konnten wir ein solches Ergebnis für DAGs erzielen, die mit dem Alphabet . Im Wesentlichen können wir zeigen, dass bei einer DAG , die große Antichains von markierten Elementen, große Antichains von markierten Elementen, aber keine großen Antichains, die sowohl viele markierte als auch markierte Elemente enthalten, eine Zersetzung von vorliegt als Partition , wobei:{a,b}GababGL1,,Ln

  • Die Partition ist das, was wir als "Schichtung" bezeichnen, dh: L1,...,Ln
    • Jedes ist eine konvexe Menge, dh wenn und dannLix,yLixzyzLi
    • für alle gibt es kein und so dassi<jxLiyLjyx
  • für jede Antichain von gibt es einige so dass in "fast enthalten" ist , dhist weniger als eine KonstanteAGiALi|ALi|
  • Für jedes gilt eine der folgenden Bedingungen: Li
    • Li enthält eine große Antichain von markierten Elementen und keine große Antichain von markierten Elementenab
    • Li enthält eine große Antichain von markierten Elementen, aber keine große Antichain von markierten Elementenba

Ferner kann eine solche Partition in PTIME berechnet werden.

Ich habe unseren aktuellen Proof online gestellt . Es ist sehr grob und im Wesentlichen nicht Korrektur gelesen, da wir das Ergebnis derzeit nicht verwenden können, aber ich dachte immer noch, es wäre ordentlicher, eine Antwort auf diese CStheory-Frage mit unseren aktuellen Fortschritten hinzuzufügen. Zögern Sie nicht, sich mit mir in Verbindung zu setzen, wenn Sie am Ergebnis interessiert sind, aber den Beweis nicht verstehen können.

a3nm
quelle