Wie finde ich die kürzeste Darstellung für eine Teilmenge eines Powersets?

13

Ich suche einen effizienten Algorithmus für das folgende Problem oder einen Beweis für die NP-Härte.

Sei ΣΣ eine Menge und A P ( Σ )AP(Σ) eine Menge von Teilmengen von ΣΣ . Finden einer Sequenz w & Sigma; *wΣ der geringsten Länge , so daß für jedes L ALA gibt es einen k NkN , so daß { w k + i | 0 i < | L | } = L{wk+i0i<|L|}=L .

Beispielsweise ist für A = { { a , b } , { a , c } }A={{a,b},{a,c}} , das Wort w = b ein Cw=bac ist eine Lösung für das Problem, da für { ein , b }{a,b} es gibt k = 0k=0 , für { a , c }{a,c} es gibt k = 1k=1 .

Was meine Motivation angeht, versuche ich, die Kanten eines endlichen Automaten darzustellen, wobei jede Kante mit einer Buchstabenfolge aus dem eingegebenen Alphabet gekennzeichnet werden kann. Ich möchte eine einzelne Zeichenfolge speichern und dann an jeder Kante ein Paar Zeiger auf diese Zeichenfolge aufbewahren. Mein Ziel ist es, die Länge dieser Zeichenfolge zu minimieren.

avakar
quelle
1
Mit anderen Worten, das Problem besteht darin, Mengen in eine Folge L 1 , ... , L n zu ordnen, die | maximiert L iL i + 1 | ? L1,,Ln|LiLi+1|
Karolis Juodelė
@ KarolisJuodelė, ich denke, das reicht nicht, da Sie für L i , L i + 1 , L i + 2 möglicherweise Elemente in L iL i + 2 zweimal in w einfügen müssen, auch wenn sie in L i sind + 1 . ZB { { a , b } , { a , c } , { a , d } } , können Sie teilen sich einLi,Li+1,Li+2LiLi+2wLi+1{{a,b},{a,c},{a,d}}azwischen den beiden ersten oder der beiden letzten, aber nicht unter allen, dem kürzesten w wäre b eine c a d . wbacad
Avakar
@ KarolisJuodelė, außerdem gibt es Fälle, in denen für einige i j , L iL j , was es noch komplizierter macht, da in einem solchen Fall die "Nachbarschaftsordnung" möglicherweise nicht vollständig ist. ijLiLj
Avakar
Nur zum Aufheitern, wenn ich die Frage richtig verstanden habe, wenn die Menge A = { { c , o , w } , { o , w , l } , { w , o , l , f } } ist , dann ein Wort c o w o w l w o l f die Anforderungen erfüllt , gegeben, aber (möglichst) mindestens eine solche Lösung ist Wort- und c O w l f ? :)A={{c,o,w},{o,w,l},{w,o,l,f}}cowowlwolfcowlf
MindaugasK
@ MindaugasK, das ist richtig, sehr schönes Beispiel :)
Avakar

Antworten:

4

Ich glaube, ich habe eine Reduktion vom Hamiltonschen Weg gefunden und damit das Problem NP-schwer bewiesen.

Nenne das Wort w Σ ein Zeuge für A , wenn es die Bedingung aus der Frage erfüllt (für jedes L A gibt es m 1, so dass { w m + i0 i < | L | } = L ) .wΣALAm1{wm+i0i<|L|}=L

Betrachten Sie die Entscheidungsversion des ursprünglichen Problems, dh entscheiden Sie, ob es für einige A und k 0 einen Zeugen für A mit einer Länge von höchstens k gibt . Dieses Problem kann gelöst werden, indem das ursprüngliche Problem als ein Orakel in Polynomzeit verwendet wird (finde den kürzesten Zeugen und vergleiche dann seine Länge mit k ).Ak0Akk

Nun zum Kern der Reduktion. Sei G = ( V , E ) ein einfacher, ungerichteter, zusammenhängender Graph. Für jedes v V sei L v = { v } { e E v e } die Menge, die den Scheitelpunkt v und alle seine benachbarten Kanten enthält. Setze Σ = E und A = { L vv V } . Dann ist GG=(V,E)vVLv={v}{eEve}vΣ=EA={LvvV}Ghat genau dann einen Hamilton-Pfad, wenn es einen Zeugen für A mit einer Länge von höchstens 2 | gibt E | + 1 .A2|E|+1

Beweis. Sei v 1 e 1 v 2e n - 1 v n ein Hamilton-Pfad in G und H = { e 1 , e 2 , , e n - 1 } die Menge aller Kanten auf dem Pfad. Für jeden Scheitelpunkt v , definiert die eingestellte U v = L vH . Wählen Sie eine beliebige Reihenfolge α v für jede U v . Das Wortv1e1v2en1vnGH={e1,e2,,en1}vUv=LvHαvUvw = & agr; v 1 e 1 & agr; v 2 e 2 ... e n - 1 & agr; v n ist ein Zeuge für A , da L v 1 durch die Teilzeichenfolge & agr; 1 e 1 , L v n durch e n - 1 & agr; n dargestellt wird und für jedes v i ist i { 1 , n } , L vw=αv1e1αv2e2en1αvnALv1α1e1Lvnen1αnvii{1,n} i durche dargestelltLvi i - 1 u v i e i . Außerdem tritt jede Kante inEzweimal inw auf,mit Ausnahme von | V | -1Kanten inH, die einmal vorkommen, und jeder Scheitelpunkt inVkommt einmal vor und ergibt | w | =2 | E | +1.ei1uvieiEw|V|1HV|w|=2|E|+1

Für die andere Richtung sei w ein beliebiger Zeuge für A mit einer Länge von höchstens 2 | E | + 1 . Es ist klar, dass jedes e E und v V in w mindestens einmal vorkommt. Man gehe ohne Einschränkung der Allgemeinheit davon aus, dass jedes e E höchstens zweimal in w und jedes v V genau einmal vorkommt; Andernfalls kann ein kürzerer Zeuge gefunden werden, indem Elemente aus w entfernt werden . Sei H E die Menge aller Kanten, die in auftretenwA2|E|+1eEvVweEwvVwHEw genau einmal. In Anbetracht der obigen Annahmen gilt Folgendes: | w | = 2 | E | - | H | + | V | .w|w|=2|E||H|+|V|

Betrachten wir eine zusammenhängende Teilzeichenfolge w der Form u e 1 e 2 ... e k v , wobei u , v V , e iE . Wir sagen, dass u , v benachbart sind. Beachten Sie, dass, wenn e iH ist , e i = { u , v } , da e i nur einmal vorkommt, es jedoch in G an zwei Eckpunkte angrenzt . Daher höchstens einer vonwue1e2ekvu,vVeiEu,veiHei={u,v}eiGeiei can be in HH. Similarly, no edge in HH can occur in ww before the first vertex or after the last vertex.

Now, there are |V||V| vertices, therefore |H||V|1|H||V|1. From there, it follows that |w|2|E|+1|w|2|E|+1. Since we assume |w|2|E|+1|w|2|E|+1, we get equality. From there we get |H|=|V|1|H|=|V|1. By pigeonhole principle, there is an edge from HH between each pair of vertices adjacent in ww. Denote h1h2hn1h1h2hn1 all elements from H in the order they appear in w. It follows that v1h1v2h2hn1vn is a Hamiltonian path in G.

Since the problem of deciding the existence of Hamiltonian path is NP-hard and the above reduction is polynomial, the original problem is NP-hard too.

avakar
quelle