Minimales Problem bei der Pfadabdeckung

Wir arbeiten in verteilten Computern und haben ein Komplexitätsproblem festgestellt, das sich auf ein Minimum an Pfadabdeckungsproblemen reduziert. Wir wissen derzeit nicht, wie wir es lösen sollen. Das Problem ist das folgende:

Sei eine ganze Zahl und sei ein Graph mit $k$ $Z_k$ Eckpunkte. Wir kennzeichnen jeden Scheitelpunkt mit einem Paarso dass. Im Folgenden benennen wir Scheitelpunkte mit ihrer Bezeichnung. Die Menge der Kanten inist wie folgt definiert: . $\frac{k(k+1)}{2}$ $(i,j)$ $1 \leq i \leq j \leq k$ $Z_k$ $\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$

Was ist die minimale Pfadabdeckung von ? $Z_k$

Lesen von "On Path Cover-Probleme in Digraphen und Anwendungen zum Programmieren von Tests" von Ntafos et al. haben wir gesehen, dass die minimale Pfadabdeckung dem Kardinal der größten unvergleichlichen Scheitelpunktmenge entspricht. Wir haben über die folgende Menge nachgedacht: mit einem Kardinal von $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ . $\frac{k^2}{4}-\frac{k}{2}$

Mit freundlichen Grüßen,

Pierre

graph-theory co.combinatorics application-of-theory Pierre
quelle

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Antworten:

Es hört sich so an, als wäre Ihr Diagramm eine transitiv geschlossene DAG, oder? Wenn ja (und dies ist wahrscheinlich eine Wiederholung dessen, was Sie in Ihrem Zitat von Ntafos et al. Sagen), ist die minimale Anzahl von Pfaden, die erforderlich sind, um die DAG abzudecken, nur die maximale Anzahl von paarweise unvergleichbaren Elementen; Dies ist Dilworths Theorem .

Ihr Beispiel mag so einfach sein, dass man diese maximal unvergleichliche Menge direkt identifizieren kann, aber im Allgemeinen ist es möglich, diese Menge in Polynomzeit durch einen Algorithmus zu finden, der auf Graph Matching basiert. Der Abschnitt "Beweis über Königs Satz" des Wikipedia-Artikels über Dilworths Satz erklärt, wie.

David Eppstein
quelle