Permutationen mit verbotenen Teilfolgen

15

Lassen Sie bezeichnen die Menge { 1 , . . . , n } und C (n, k) bezeichnen die Menge aller k- Kombinationen von Elementen aus [ n ] ohne Wiederholung. Sei p = p 1 p 2 . . . p k ist ein k- Tupel in C ( n , k ) . Wir sagen, dass eine Permutation π : [ n ] [ n[n]{1,...,n}k[n]p=p1p2...pkkC(n,k) der Mengeπ:[n][n] vermeidet p, wenn es kein k-Tupel von ganzen Zahlen i 1 < i 2 <gibt . . . < i k so dass π ( i 1 ) = p 1 ,[n]pi1<i2<...<ik

π(i1)=p1,π(i2)=p2,...,π(ik)=pk.

Wenn beispielsweise dann vermeidet die Permutation 12453 134 als eine Untersequenz , während die Permutation 1 2 3 5 4 dies nicht tut.n=51245313412354

Frage: Sei eine Konstante. Wenn eine Menge S C ( n , k ) von k- Tupeln gegeben ist, finde eine Permutation π : [ n ] [ n ] , die jedes k- Tupel in S vermeidet . kSC(n,k)kπ:[n][n]kS

  1. Gibt es einen Algorithmus für dieses Problem, der in polynomial ist ? P | und n ? Hier ist n unär gegeben. Ein Algorithmus, der zur Zeit n f ( k ) | läuft P | g ( k ) wäre in Ordnung.|P|nnnf(k)|P|g(k)
  2. Oder ist dieses Problem NP-vollständig?

Hinweise auf dieses Problem oder Vorschläge für Algorithmen sind willkommen. Es ist zu beachten, dass der oben definierte Begriff der Permutationsvermeidung nicht mit dem Begriff der Permutationsvermeidung identisch ist, bei dem nur die relative Reihenfolge der Elemente wichtig ist und der in der Kombinatorik gut untersucht zu sein scheint.

Mateus de Oliveira Oliveira
quelle
Meinen Sie damit, dass Sie eine Permutation zufällig auswählen und überprüfen, ob sie keine Einschränkungen in S verletzt? Ein randomisierter polynomieller Zeitalgorithmus wäre besser als nichts. k wird als Konstante angenommen, ist also per definitionem klein. Aber ich verstehe nicht, wie es effizient funktionieren würde, wenn S viele Einschränkungen hätte. Da nach Davids Antwort das Problem NPC für k = 3 ist, bin ich ein bisschen skeptisch, ob ein randomisierter Algorithmus effizient ist. Könnten Sie bitte Ihre Idee ein wenig erläutern?
Mateus de Oliveira Oliveira
Entschuldigung, ich habe übersehen, dass Sie eine Reihe verbotener Tupel haben. Es gibt keine Garantie dafür, dass die Probenahme bei Ablehnung effizient ist.
DW

Antworten:

13

Es ist NP-vollständig für durch eine Reduktion von der Zwischenzeit . In dem Zwischen-Gleichheitsproblem werden einem n Gegenstände gegeben, die vollständig zu ordnen sind, und Einschränkungen für einige Dreifache von Gegenständen, die einen Gegenstand des Dreifachen zwingen, zwischen den anderen beiden zu sein. In Ihrem Problem kann dieselbe Einschränkung erzwungen werden, indem alle Untersequenzen für drei Elemente verboten werden, bei denen das mittlere Element nicht in der Mitte liegt. Es ist jedoch bekannt, dass die Übereinstimmung NP-vollständig ist: siehe J. Opatrny, Total ordering problem, SIAM J. Comput. 8 (1979), 111–114.k=3n

David Eppstein
quelle