Härte eines Untergehäuses von Set Cover

10

Wie schwer ist das Set Cover-Problem, wenn die Anzahl der Elemente durch eine Funktion (z. B. ) begrenzt ist, wobei die Größe der Probleminstanz ist. Formal,lognn

Sei und wobei und . Wie schwer ist es, das folgende Problem zu entscheiden?U={e1,,em}F={S1,,Sn}SiUm=O(logn)

SET-COVER'={<U,F,k>: there exists at most k subsets  Si1,,SikF that cover U}.

Was ist, wenn ?m=O(n)

Jedes Ergebnis, das auf bekannten Vermutungen basiert (z. B. Unique Games, ETH), ist gut.

Bearbeiten 1: Eine Motivation für dieses Problem besteht darin, herauszufinden, wann das Problem mit zunehmendem schwierig wird. Das Problem liegt eindeutig in P, wenn und NP-hart, wenn . Was ist die Schwelle für die NP-Härte des Problems?mm=O(1)m=O(n)

Edit 2: Es gibt einen trivialen Algorithmus, um ihn in der Zeit zu bestimmen (der alle Teilmengen der Größe von ). Daher ist das Problem nicht NP-hart, wenn da die ETH impliziert, dass es in der Zeit keinen Algorithmus für NP-hart gibt Problem (wobei die Größe des NP-harten Problems ist).O(nm)mFm=O(logn)O(2no(1))n

user1297
quelle
2
Es gibt einen besseren Algorithmus, um das Problem in der Zeit zu bestimmen (genauer die Bell-Zahl für ): Testen Sie für jede Partition der Elemente in Teilmengen, ob es eine Eingabemenge gibt, die jede Teilmenge abdeckt. Für das Problem also in Polynomzeit gelöst werden. Dies beantwortet Ihre Frage zu jedoch nicht ganz . mO(m)mm=O(logn/loglogn)m=O(logn)
David Eppstein

Antworten:

11

Wenn , können Sie die dynamische Programmierung verwenden, um das Optimum in der Polynomzeit zu finden. Die Tabelle enthält Boolesche Zellen für jede und , die angeben, ob es Mengen gibt, die das abdecken Elemente in .T , X{ 0 , , k } X UX.m=O(logn)T,X{0,,k}XUX

Wenn , sagen wir , bleibt das Problem NP-schwer. Fügen Sie bei einer Instanz von SET-COVER neue Elemente und neue Mengen hinzu, die aus nicht leeren Teilmengen der neuen Elemente bestehen, einschließlich (wenn groß genug ist, ). Erhöhen Sie auch um eins. Die neuen sind und .mCm=O(n) mx1,...,xm(2C - 1 m)2{x1,...,xm}m(2C - 1 m)2<2mkm,nm'=2mn'=n+(2C - 1 m)2mCnmx1,,xm(2C1m)2{x1,,xm}m(2C1m)2<2mkm,nm=2mn=n+(2C1m)2(C1m)2

Yuval Filmus
quelle
Allgemeiner ist der Fall NP-hart, und der Fall ist unter der Annahme der ETH nicht NP-hart, da es ein Algorithmus. m = n o ( 1 ) p o l y ( n , 2 m )m=nO(1)m=no(1)poly(n,2m)
Yuval Filmus
11

Der Fall von ist in Zeit, wie von Yuval angegeben, aber auch für Sie das Problem in lösen. Zeit (Polynomzeit) durch erschöpfende Suche. Unter der Annahme der Hypothese der starken exponentiellen Zeit (dass CNF-SAT für Formeln mit Variablen und -Klauseln mindestens Zeit benötigt) sind diese beiden Zeitgrenzen die "Grenze" dessen, was wir erwarten können in der Polynomzeit im folgenden Sinne.n O ( c ) k = O ( 1 ) O ( n km ) N O ( N ) 2 N - o ( N )m=clognnO(c)k=O(1)O(nkm)NO(N)2No(N)

In meiner SODA'10-Arbeit mit Mihai Patrascu untersuchen wir das im Wesentlichen isomorphe Problem, eine dominierende Menge der Größe in einem beliebigen Knoten-Graphen zu finden, und zeigen, dass wenn dominierende Menge in gelöst werden kann Zeit für einige und , dann gibt es einen -Zeitalgorithmus für CNF-SAT für Variablen und Klauseln.knknkεk2ε>02N(1ε/2)poly(M)NM

Wenn Sie die Beziehung zwischen den Nachbarschaften von Eckpunkten in einer dominierenden Mengeninstanz und den Mengen in einer Mengendeckungsinstanz notieren und die Reduktion untersuchen, werden Sie feststellen, dass diese Reduktion auch das Lösen von Set Cover mit Mengen über ein Universum der Größe in Zeit impliziert einen CNF-SAT-Algorithmus für CNF-Formeln mit Klauseln und Variablen, die in Zeit ausgeführt werden . Um die Starke ETH zu widerlegen, reicht es aus, CNF-SAT für den Fall zu lösen, dass . Daher ein Algorithmus für Ihr Problem, der inn m n k - εf ( m ) M N 2 N ( 1 - ε / 2 )f ( M ) M = O ( N ) n k - ε2 m / α ( m ) α ( m )knmnkεf(m)MN2N(1ε/2)f(M)M=O(N)nkε2m/α(m)Zeit für eine unbegrenzte Funktion würde einen überraschenden neuen SAT-Algorithmus ergeben.α(m)

Ryan Williams
quelle