Dopasowanie trójwymiarowe

Dopasowania trójwymiarowe. (a) Wprowadź T. (b)–(c) Rozwiązania.

W dyscyplinie matematycznej , jaką jest teoria grafów , dopasowanie trójwymiarowe jest uogólnieniem dopasowania dwustronnego (znanego również jako dopasowanie dwuwymiarowe) do hipergrafów trzyczęściowych , które składają się z hipergrafów, z których każdy zawiera 3 wierzchołki (zamiast krawędzi zawierających 2 wierzchołki zwykłego grafu).

Dopasowanie 3-wymiarowe, często określane skrótem 3DM , to także nazwa dobrze znanego problemu obliczeniowego: znalezienia największego dopasowania 3-wymiarowego w danym hipergrafie. 3DM jest jednym z pierwszych problemów, które okazały się NP-trudne .

Definicja

Niech X , Y i Z będą zbiorami skończonymi i niech T będzie podzbiorem X × Y × Z . Oznacza to, że T składa się z trójek ( x , y , z ) takich, że x ∈ X , y ∈ Y , oraz z ∈ Z . Teraz M ⊆ T jest trójwymiarowym dopasowaniem, jeśli zachodzi następująca zasada: dla dowolnych dwóch różnych trójek ( x 1 , y 1 , z 1 ) ∈ M i ( x 2 , y 2 , z 2 ) ∈ M , mamy x 1 ≠ x 2 , y 1 ≠ y 2 , oraz z 1 ≠ z 2 .

Przykład

Rysunek po prawej ilustruje trójwymiarowe dopasowania. Zestaw X jest oznaczony czerwonymi kropkami, Y jest oznaczony niebieskimi kropkami, a Z jest oznaczony zielonymi kropkami. Rysunek (a) przedstawia zbiór T (szare obszary). Rysunek (b) przedstawia trójwymiarowe dopasowanie M z | M | = 2, a rysunek (c) przedstawia trójwymiarowe dopasowanie M z | M | = 3.

Dopasowanie M zilustrowane na rysunku (c) jest maksymalnie trójwymiarowym dopasowaniem , tj. maksymalizuje | M |. Dopasowania pokazane na rysunkach (b)–(c) są maksymalnymi dopasowaniami trójwymiarowymi , tj. nie można ich rozszerzyć, dodając kolejne elementy z T .

Oto przykładowa interaktywna wizualizacja w javascript

Porównanie z dopasowaniem dwustronnym

Dopasowanie dwuwymiarowe można zdefiniować w zupełnie analogiczny sposób. Niech X i Y będą zbiorami skończonymi i niech T będzie podzbiorem X × Y . Teraz M ⊆ T jest dopasowaniem dwuwymiarowym, jeśli zachodzi następująca zasada: dla dowolnych dwóch różnych par ( x 1 , y 1 ) ∈ M i ( x 2 , y 2 ) ∈ M , mamy x 1 ≠ x 2 i y 1 ≠ y 2 .

W przypadku dopasowania dwuwymiarowego zbiór T można interpretować jako zbiór krawędzi w grafie dwudzielnym G = ( X , Y , T ); każda krawędź w T łączy wierzchołek w X z wierzchołkiem w Y . Dopasowanie dwuwymiarowe jest zatem dopasowaniem w grafie G , czyli zbiorem parami niesąsiadujących ze sobą krawędzi.

Stąd trójwymiarowe dopasowania można interpretować jako uogólnienie dopasowań do hipergrafów: zbiory X , Y i Z zawierają wierzchołki, każdy element T jest hiperkrawędzią, a zbiór M składa się z parzystych niesąsiadujących ze sobą krawędzi (krawędzie, które nie mają wspólnego wierzchołka). W przypadku dopasowania dwuwymiarowego mamy Y = Z.

Porównanie z opakowaniem zestawu

Dopasowanie trójwymiarowe jest szczególnym przypadkiem pakowania zbioru : możemy interpretować każdy element ( x , y , z ) zbioru T jako podzbiór { x , y , z } zbioru X ∪ Y ∪ Z ; wówczas trójwymiarowe dopasowanie M składa się z parami rozłącznych podzbiorów.

Kwestia decyzji

W teorii złożoności obliczeniowej trójwymiarowe dopasowywanie (3DM) to nazwa następującego problemu decyzyjnego : mając zbiór T i liczbę całkowitą k , zdecyduj, czy istnieje trójwymiarowe dopasowanie M ⊆ T z | M | ≥ k .

Wiadomo, że ten problem decyzyjny jest NP-zupełny ; jest to jeden z 21 problemów NP-zupełnych Karpa . Jest NP-zupełny nawet w szczególnym przypadku, gdy k = | X | = | Y | = | Z | oraz gdy każdy element zawiera się w dokładnie 3 zbiorach, tj. gdy chcemy idealnego dopasowania w 3-regularnym hipergrafie. W tym przypadku trójwymiarowe dopasowanie to nie tylko opakowanie zestawu, ale także dokładne pokrycie : zestaw M obejmuje każdy element X , Y i Z dokładnie raz. Dowód jest przez redukcję z 3SAT . Biorąc pod uwagę instancję 3SAT, konstruujemy instancję 3DM w następujący sposób:

  • Dla każdej zmiennej x i istnieje „zmienny gadżet” w kształcie koła. Składa się z nakładających się na siebie trojaczków. Liczba trójek jest dwukrotnie większa od liczby wystąpień x i we wzorze. Istnieją dokładnie dwa sposoby na pokrycie wszystkich wierzchołków w gadżecie: jeden polega na wybraniu wszystkich trojaczków o indeksie parzystym, a drugi to wybranie wszystkich trojaczków o indeksie nieparzystym. Te dwa sposoby odpowiadają ustawieniu x i na „prawda” lub „fałsz”. Wybór „prawdziwy” pozostawia odkryty dokładnie jeden wierzchołek w każdej trójce o indeksie nieparzystym, a wybór „fałszywy” pozostawia odkryty dokładnie jeden wierzchołek w każdym trójce o indeksie parzystym.
  • Dla każdej klauzuli x i u x j u x k istnieje „gadżet klauzuli” w kształcie róży. Składa się z trzech zachodzących na siebie trójek, po jednej dla każdej zmiennej w klauzuli. Może być zasłonięty, jeśli co najmniej jeden z węzłów pozostanie odsłonięty przez wybór zmiennych gadżetów.
  • Ponieważ możliwe jest, że dwa lub więcej węzłów pozostanie odkrytych, potrzebujemy również „gadżetu do zbierania śmieci”. Ma kształt większej róży. Składa się z kilku zachodzących na siebie trójek, po jednej dla każdego wierzchołka, który można pozostawić odkryty w gadżecie zmiennej. Liczba takich gadżetów jest ustalana tak, aby można było je objąć dokładnie wtedy i tylko wtedy, gdy istnieje satysfakcjonujące zlecenie.

Przypadki specjalne

Istnieją wielomianowe algorytmy czasu do rozwiązywania 3DM w gęstych hipergrafach.

Kwestia optymalizacji

Maksymalne dopasowanie trójwymiarowe to największe dopasowanie trójwymiarowe. W teorii złożoności obliczeniowej jest to również nazwa następującego problemu optymalizacyjnego : biorąc pod uwagę zbiór T , znajdź trójwymiarowe dopasowanie M ⊆ T , które maksymalizuje |M| .

Ponieważ opisany powyżej problem decyzyjny jest NP-zupełny, ten problem optymalizacji jest NP-trudny , a zatem wydaje się, że nie ma algorytmu czasu wielomianowego do znajdowania maksymalnego trójwymiarowego dopasowania. Istnieją jednak wydajne algorytmy czasu wielomianowego do znajdowania maksymalnego dopasowania dwudzielnego (maksymalnego dopasowania 2-wymiarowego), na przykład algorytm Hopcrofta – Karpa .

Algorytmy aproksymacyjne

Istnieje bardzo prosty algorytm 3-aproksymacji w czasie wielomianowym dla dopasowywania trójwymiarowego: znajdź dowolne maksymalne dopasowanie trójwymiarowe. Tak jak maksymalne dopasowanie mieści się w zakresie współczynnika 2 maksymalnego dopasowania, maksymalne dopasowanie trójwymiarowe mieści się w zakresie współczynnika 3 maksymalnego dopasowania trójwymiarowego.

Dla dowolnej stałej ε > 0 istnieje algorytm aproksymacji w czasie wielomianowym (4/3 + ε) do trójwymiarowego dopasowania.

Jednak osiągnięcie lepszych współczynników przybliżenia jest prawdopodobnie trudne: problem jest APX-zupełny , to znaczy trudno jest go przybliżyć w ramach jakiejś stałej.

Jest NP-trudne osiągnięcie współczynnika aproksymacji 95/94 dla maksymalnego dopasowania 3-d i współczynnika aproksymacji 48/47 dla maksymalnego dopasowania 4-d. Twardość pozostaje nawet wtedy, gdy jest ograniczona do przypadków z dokładnie dwoma wystąpieniami każdego pierwiastka.

Algorytmy równoległe

Istnieją różne algorytmy dopasowywania 3-D w modelu obliczeń masowo równoległych .

Zobacz też

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=3-dimensional_matching&oldid=1139140729 ”