3차원 매칭

3-dimensional matching
3차원 매칭 (a) 입력 T. (b)– (c) 솔루션

그래프 이론의 수학 분야에서, 3차원 매칭은 초당 매칭(2차원 매칭이라고도 함)과 3분할 하이퍼그래프의 일반화이다. 하이퍼그래프는 각각이 (통상적인 그래프에서 2개의 정점을 포함하는 가장자리 대신) 3개의 정점을 포함하는 하이퍼그래프로 구성된다.

3차원 매칭은 종종 3DM으로 줄여 쓰기도 하는데, 이는 잘 알려진 계산 문제의 이름입니다. 즉, 주어진 하이퍼그래프에서 가장 큰 3차원 매칭을 찾는 것입니다. 3DM은 NP-hard로 판명된 첫 번째 문제 중 하나입니다.

정의.

X, Y, Z를 유한 집합으로 하고, T를 X × Y × Z의 부분 집합으로 하자.즉, T는 x x X, y y Y 및 z z Z와 같은 3배(x, y, z)로 구성됩니다.M1 t T는 다음 두 개의 서로 다른 트리플(x1, y1, z) and M 및 (x22, y22, z) , M에 대해 x x21 x, y , y 및 z1 z2 z를 갖는1 경우 3차원 일치입니다.

예

오른쪽 그림은 3차원 매칭을 보여줍니다.세트 X는 빨간색 점, Y는 파란색 점, Z는 녹색 점으로 표시됩니다.그림(a)은 설정된 T(회색 영역)를 나타냅니다.그림 (b)는 M = 2의 3차원 일치, 그림 (c)는 M = 3의 3차원 일치이다.

그림 (c)에 나타낸 일치 M은 최대 3차원 일치이다. 즉, M을 최대화한다. 그림 (b)–(c)에 나타낸 일치 M은 최대 3차원 일치이다. 즉, T의 요소를 더하여 확장할 수 없다.

다음은 javascript의 대화형 시각화 예제입니다.

초당 매칭과의 비교

2차원 매칭은 완전히 유사한 방법으로 정의할 수 있다.X와 Y를 유한 집합으로 하고, T를 X × Y의 부분 집합으로 합니다. 이제 M t T는 2차원 매칭입니다. 임의의 두 개의 다른 쌍(x1, y1) m M과 (x2, y2) m M에 대해 x x2 x와1 y y2 y가 있습니다1.

2차원 매칭의 경우, 세트 T는 초당 그래프 G = (X, Y, T)의 에지 세트로 해석할 수 있다.T의 각 에지는 X의 정점과 Y의 정점을 연결한다.그 후 2차원 매칭은 그래프 G의 매칭, 즉 현명하지 않은 쌍의 에지 세트이다.

따라서 3차원 매칭은 하이퍼그래프와의 매칭의 일반화로서 해석할 수 있다.X, Y 및 Z는 정점을 포함하고 T의 각 요소는 하이퍼게이지이며, 세트 M은 쌍으로 이루어진 비인접 에지(공통 정점을 가지지 않는 에지)로 구성되어 있다.2차원 매칭의 경우 Y = Z가 있습니다.

세트 패킹과의 비교

3차원 매칭은 세트 패킹의 특별한 경우입니다.T의 각 요소(x, y, z)를 X y Y z Z의 서브셋 {x, y, z}으로 해석할 수 있습니다.그 후 3차원 매칭 M은 쌍으로 분리된 서브셋으로 구성됩니다.

의사결정 문제

계산 복잡도 이론에서, 3차원 매칭(3DM)은 다음의 결정 문제의 이름입니다. 집합 T와 정수 k가 주어졌을 때, M k k와 3차원 매칭 M m T가 존재하는지 여부를 판단하십시오.

이 결정 문제는 NP-완전이라고 알려져 있으며 Karp의 21개의 NP-완전 문제 [1]중 하나입니다.k = X = Y = Z라는 특수한 경우에도 NP-완전이며, 각 원소가 정확히 3세트(즉, 3-규칙 하이퍼그래프에서 [1][2][3]완벽한 일치를 원할 때)에 포함되는 경우에도 NP-완전이다.이 경우, 3차원 매칭은 세트 패킹일 뿐만 아니라 정확한 커버이기도 합니다.세트 M은 X, Y, Z의 각 요소를 [4]1회 정확하게 커버합니다.그 증거는 3SAT에서 축소된 것이다.3SAT 인스턴스를 지정하면 다음과 [2][5]같이 3DM 인스턴스를 구축합니다.

  • 각 변수i x에 대해 바퀴 모양의 "가변 가젯"이 있습니다.그것은 겹치는 세쌍둥이로 만들어졌다.세쌍둥이의 수는 공식에서 x의 발생i 횟수의 두 배입니다.가젯의 모든 정점을 커버하는 방법은 정확히 두 가지가 있습니다. 하나는 모든 짝수색인 세쌍둥이를 선택하는 것이고, 다른 하나는 홀수색인 세쌍둥이를 선택하는 것입니다.이 두 가지 방법은 x를 "true" 또는 "false"로 설정하는i 것에 해당합니다."참" 선택은 홀수 색인 세쌍둥이마다 정확히 하나의 정점을 드러내고, "거짓" 선택은 짝수 색인 세쌍둥이마다 정확히 하나의 정점을 드러냅니다.
  • 각 절i x uj x uk x에는 장미 모양의 "일시정지 가젯"이 있습니다.절의 각 변수마다 하나씩 세 개의 겹치는 세 개의 세 개의 세 개의 세 개로 구성됩니다.가변 가젯의 선택에 의해 노드 중 적어도1개가 검출되지 않은 채로 있는 경우, 이 문제는 커버될 수 있습니다.
  • 2개 이상의 노드가 커버되지 않은 채로 있을 가능성이 있기 때문에, 「쓰레기 수집 장치」도 필요합니다.그것은 더 큰 장미처럼 생겼다.이것은 여러 겹치는 세쌍둥이로 이루어져 있는데, 각 정점에 하나씩은 가변 가젯에서 덮개를 벗긴 채로 둘 수 있습니다.이러한 가젯의 수는 할당이 만족스러운 경우에만 정확하게 커버될 수 있도록 결정됩니다.

특수한 경우

고밀도 하이퍼그래프에서 [6][7]3DM을 해결하기 위한 다항식 시간 알고리즘이 있습니다.

최적화 문제

최대 3차원 매칭은 최대 3차원 매칭입니다.계산 복잡도 이론에서, 이것은 다음 최적화 문제의 이름이기도 하다: 집합 T가 주어졌을 때, M을 최대화하는 3차원 일치 M m T를 찾아라.

위의 판정 문제는 NP-완전이기 때문에 이 최적화 문제는 NP-hard이므로 최대 3차원 매칭을 구하는 다항식 시간 알고리즘은 없는 것으로 보인다.그러나 최대 초당 일치(2차원 일치)를 찾기 위한 효율적인 다항 시간 알고리즘이 있습니다. 예를 들어 홉크로프트-카르프 알고리즘입니다.

근사 알고리즘

3차원 매칭을 위한 매우 간단한 다항식-시간 3-근사 알고리즘이 있습니다: 최대 3차원 [8]매칭을 찾습니다.최대 매칭이 최대 [9]매칭의 계수 2 내에 있듯이 최대 3차원 매칭은 최대 3차원 매칭의 계수 3 내에 있다.

모든 상수 θ > 0에 대해 3차원 [10]매칭을 위한 다항식 시간(4/3 + θ)-근사 알고리즘이 있다.

그러나 더 나은 근사 계수를 얻는 것은 어려울 수 있습니다. 문제는 APX-완전, 즉 일정한 [11][12][8]범위 내에서 근사하는 것이 어렵습니다.

최대 3-d 매칭의 경우 95/94의 근사 계수를, 최대 4-d 매칭의 경우 48/47의 근사 계수를 달성하는 것은 NP-hard입니다.각 [13]요소가 정확히 2개씩 발생하는 인스턴스로 제한되는 경우에도 경도는 유지됩니다.

병렬 알고리즘

Massively parallel 연산 [14]모델에는 3D 매칭을 위한 다양한 알고리즘이 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ a b 카르프(1972년).
  2. ^ a b 섹션 3.1 및 부록 A.3.1의 문제 SP1Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.
  3. ^ 섹션 15.5Korte, Bernhard; Vygen, Jens (2006), Combinatorial Optimization: Theory and Algorithms (3rd ed.), Springer.
  4. ^ Papadimitriou & Steiglitz(1998), 섹션 15.7.
  5. ^ Demaine, Erik (2016). "16. Complexity: P, NP, NP-completeness, Reductions". YouTube.{{cite web}}: CS1 maint :url-status (링크)
  6. ^ Karpinski, Rucinski & Szymanska (2009)
  7. ^ Keevash, Knox & Microft (2013)
  8. ^ a b 칸(1991)
  9. ^ 매칭(그래프 이론)#프로퍼티
  10. ^ Cygan, Marek (2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". IEEE 54th Annual Symposium on Foundations of Computer Science: 509–518. arXiv:1304.1424. Bibcode:2013arXiv1304.1424C. doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646.
  11. ^ 크레센지 외 (2000).
  12. ^ Ausiello 등 (2003), 부록 B의 문제 SP1.
  13. ^ Chlebík, Miroslav; Chlebíková, Janka (2006-04-04). "Complexity of approximating bounded variants of optimization problems". Theoretical Computer Science. Foundations of Computation Theory (FCT 2003). 354 (3): 320–338. doi:10.1016/j.tcs.2005.11.029. ISSN 0304-3975.
  14. ^ Hanguir, Oussama; Stein, Clifford (2020-09-21). "Distributed Algorithms for Matching in Hypergraphs". arXiv:2009.09605 [cs.DS].

레퍼런스