Auswählen von Kosets

Question

Ich habe beim Experimentieren mit Klassifizierungsalgorithmen in das folgende algorithmische Problem gelaufen. Elemente werden in eine Polyhierarchie klassifiziert, was ich mit einer einzigen Wurzel ein Poset darstellt. Ich muss das folgende Problem lösen, das viel aussieht wie das Deckungsproblem set.

Ich habe mein Latex-ED-Problem hochgeladen. Beschreibung hier .

Einen Annäherungsalgorithmus erwenden, der 1 & 2 erfüllt, ist ziemlich einfach, starten Sie einfach an den Scheitelpunkten von G und "Gehen Sie nach oben" oder beginnen Sie an der Wurzel und "Gehen Sie hinunter". Angenommen, Sie starten am Wurzel, kompenative Scheitelpunkte ausdehnen und dann unnötige Scheitelpunkte entfernen, bis Sie mindestens k Untergitter haben. Die Annäherungsgrenzen hängt von der Anzahl der Kinder eines Scheitelpunkts ab, was für meine Anwendung in Ordnung ist.

weiß jemand, ob dieses Problem einen richtigen Namen hat oder vielleicht die Baumversion des Problems? Ich würde mich daran interessieren, herauszufinden, ob dieses Problem np-hart ist, vielleicht hat jemand Ideen für ein gutes NP-Hard-Problem, um einen Polynomalgorithmus zu reduzieren oder aufzuwarten, um das Problem zu lösen. Wenn Sie beide sammeln Ihren Millionen Dollar Preis . ;)

Answer 1

Die DAG-Version ist hart um (Trommelrolle) eine Reduktion von der SET-Abdeckung.Set k= 2 und tue das offensichtliche: Zustand (2) verhindert, dass wir die Wurzel nehmen.(Beachten Sie, dass (3) nicht eigentlich (2) aufgrund der unteren Grenze k.)

Die Baumversion ist ein Sonderfall der Serien-Parallel-Poset-Version, die genau in der Polynomzeit gelöst werden kann.Hier ist eine rekursive Formel, die ein Polynom p (x) ergibt, in dem der Koeffizient von X ^{n die Anzahl der Abdeckungen der Kardinalität n ist.}

einzelner Scheitelpunkt wird abgedeckt: p (x)= x.

Andere Scheitelpunkt: P (x)= 1 + x.

Parallelzusammensetzung, wobei q und r die Polynome für die beiden Posen sind: q (x) r (x).

Serienzusammensetzung, wobei q das Polynom für das obere Poset und R ist, für den Boden: Wenn der obere Poset keine abgedeckten Scheitelpunkte enthält, dann p (x)= (q (q (x) - 1) + r (x);Ansonsten p (x)= q (x).