Härte eines Untergehäuses von Set Cover

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,$\log n$$n$

Sei und wobei und . Wie schwer ist es, das folgende Problem zu entscheiden?$\mathcal{U}=\{e_1, \cdots, e_m\}$$\mathcal{F} = \{S_1, \cdots, S_n\}$$S_i \subseteq \mathcal{U}$$m = O(\log n)$

Was ist, wenn ?$m=O(\sqrt{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?$m$$m=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(n^{m})$$m$$\mathcal{F}$$m=O(\log{n})$$O(2^{n^{o(1)}})$$n$

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 ⊆ U ℓ $m = O(\log n)$$T_{\ell,X}$$\ell \in \{0,\ldots,k\}$$X \subseteq \mathcal{U}$$\ell$$X$

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 .m≤C$m = O(\sqrt{n})$ mx1,...,xm(2C - 1 m)2{x1,...,xm}m(2C - 1 m)2<2mkm,nm'=2mn'=n+(2C - 1 m)2$m \leq C\sqrt{n}$$m$$x_1,\ldots,x_m$$(2C^{-1}m)^2$$\{x_1,\ldots,x_m\}$$m$$(2C^{-1}m)^2 < 2^m$$k$$m,n$$m' = 2m$$n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$

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 k ≤ m ) N O ( N ) 2 N - o ( N $m = c \log n$$n^{O(c)}$$k = O(1)$$O(n^k \cdot m)$$N$$O(N)$$2^{N-o(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.$k$$n$$k$$n^{k-\varepsilon}$$k \geq 2$$\varepsilon > 0$$2^{N(1-\varepsilon/2)}poly(M)$$N$$M$

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 $k$$n$$m$$n^{k-\varepsilon}\cdot f(m)$$M$$N$$2^{N(1-\varepsilon/2)}\cdot f(M)$$M = O(N)$$n^{k-\varepsilon}\cdot 2^{m/\alpha(m)}$Zeit für eine unbegrenzte Funktion würde einen überraschenden neuen SAT-Algorithmus ergeben.$\alpha(m)$