NP-Härte der Abdeckung mit rechteckigen Teilen (Google Hash Code 2015 Testrunde)

In der Testrunde zum Google Hash Code 2015 ( Problemstellung ) wurde nach folgendem Problem gefragt:

• Eingabe: ein Gitter mit einigen markierten Quadraten, eine Schwelle T ∈ N , eine maximale Fläche A ∈ $M$$T \in \mathbb{N}$$A \in \mathbb{N}$
• Ausgabe: Die größtmögliche Gesamtfläche eines Satzes disjunkter Rechtecke mit ganzzahligen Koordinaten in so dass jedes Rechteck mindestens T markierte Quadrate enthält und jedes Rechteck höchstens A Fläche hat .$M$$T$$A$

In der Terminologie von Google ist das Raster eine Pizza, die markierten Quadrate sind Schinken und die disjunkten Rechtecke sind Scheiben.

Wir können dieses Problem eindeutig in ein Entscheidungsproblem umformulieren, indem wir eine zusätzliche Eingabe hinzufügen und die Antwort lauten: " Gibt es eine Menge disjunkter Rechtecke, die die Bedingungen erfüllen, deren Gesamtfläche mindestens n Quadrate beträgt ?".$n \in \mathbb{N}$$n$

Meine Frage: Während das Google-Problem die Kandidaten gebeten hat, eine Lösung zu finden, die "so gut wie möglich" für das Berechnungsproblem in einer bestimmten Instanz ist, halte ich es für wahrscheinlich, dass das allgemeine Problem (in seiner Entscheidungsformulierung) NP-vollständig ist. Ich kann jedoch keine Reduktion finden, um die NP-Härte zu zeigen. (Die NP-Mitgliedschaft erfolgt sofort.) Wie kann man beweisen, dass dieses Problem NP-schwer ist?

Es folgen einige Beispiele, um das Problem zu veranschaulichen. Betrachten wir das von 4 grid { 0 , 1 , 2 , 3 } × { 0 , 1 , 2 , 3 $4$$4$$\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$ , mit markierten Plätzen , ( 0 , 2 ) und ( 2 , 2 ) , graphisch dargestellt mit um markierte Quadrate anzuzeigen:$(1, 1)$$(0, 2)$$(2, 2)$X

..X.
.X..
..X.
....

Setzen Sie (Rechtecke mit höchstens 6 Quadraten) und T = 1 (mindestens ein markiertes Quadrat pro Rechteck). Eine optimale Lösung (die das gesamte Raster abdeckt) besteht darin, die folgenden Rechtecke zu verwenden:$A = 6$$6$$T = 1$

aaAa
bBcc
bbCc
bbcc

Im folgenden Raster mit und T = 2 :$A = 3$$T = 2$

XXX
.X.
...

Man kann es nicht besser machen, als nur drei Quadrate abzudecken:

AAA
.X.
...

oder

XBX
.B.
.b.

(Denken Sie daran, dass sich Rechtecke in der Partition nicht überlappen können.)

Mit anderen Leuten, die sich mit dieser Frage befassten, versuchten wir, die Verpackung von Behältern zu reduzieren, um Probleme, 3-SAT- und Hamilton-Zyklen abzudecken, und es gelang uns nicht, einen zum Laufen zu bringen.

Dies ist eine Skizze einer Verkleinerung von MONOTONE CUBIC PLANAR 1-3 SAT:

$\varphi = C_1 \land C_2 \land ... \land C_m$$C_j$$C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$
$\varphi$$C_j$ enthält genau ein wahres Literal.

Das Problem bleibt NP-vollständig, selbst wenn alle Literale in den Klauseln positiv sind (MONOTONE), wenn die grafisch erstellten Verbindungsklauseln mit Variablen planar (PLANAR) sind und jede Variable in genau 3 Klauseln (CUBIC) enthalten ist (C. Moore und JM Robson, Probleme mit harten Fliesen mit einfachen Fliesen, Discrete Comput. Geom. 26 (2001), 573-590.).

$T=3, A=6$

$A$$+$$-$

$x_i$$x_i = TRUE$$x_i = FALSE$

$C_j$$L_{i,1}, L_{i,2}, L_{i,3}$

Schließlich können wir Shift- und Turn-Gadgets erstellen, um die Signale gemäß dem zugrunde liegenden planaren Diagramm zu übertragen und die Endpunkte anzupassen:

$H$$A$

Wenn die ursprüngliche 1-3 SAT-Formel erfüllt werden kann, können wir konstruktionsbedingt schneiden$H /3$$A H / 3$

$H /3$$A H / 3$ ) bleibt kein Schinken unbedeckt, und die Signale auf den Variablen-Gadgets und auf den Klauseln sind konsistent: Der Schinken auf der Klausel ist abgedeckt durch genau eine positive Schicht, die von einer positiven Variablen stammt, und jede Variable erzeugt 3 positive oder 3 negative Signale (keine gemischten Signale); Die Schnitte führen also zu einer gültigen 1-3 SAT-Zuordnung.