FKT 알고리즘

FKT algorithm

Fisher, Kastelyn, Thermley의 이름을 딴 FKT 알고리즘은 다항식 시간으로 평면 그래프의 완벽한 일치 횟수를 카운트한다.이 작업은 일반 그래프의 경우 #P-완전이다.완전할 필요가 없는 일치의 경우, 일람표 그래프에서도 #P-완전성을 유지한다.FKT 알고리즘의 핵심 아이디어는 문제를 그래프의 평면 임베딩에서 도출된 스큐 대칭 행렬의 파피안 연산으로 변환하는 것이다.이 매트릭스의 Pafeian은 표준 결정인자 알고리즘을 사용하여 효율적으로 계산된다.

역사

평면적 완벽한 짝을 세는 문제는 통계 역학과 화학에 그 뿌리를 두고 있는데, 여기서 원문은 바로 이원자 분자가 표면에 흡착되어 하나의 층을 이루게 되면, 얼마나 많은 방법을 배열할 수 있는가 하는 것이었다.[1]칸막이 함수는 평형 상태에서 시스템의 통계적 특성을 인코딩하는 중요한 수량이며 앞의 질문에 답하는 데 사용할 수 있다.그러나 파티션 함수를 그 정의에서 계산하려고 하는 것은 실용적이지 않다.따라서 물리적 시스템을 정확하게 해결하는 것은 정확히 계산하기에 충분히 간단한 특정 물리적 시스템에 대한 파티션 함수의 대체 형식을 찾는 것이다.[2]1960년대 초, 정확히 해결할 수 있는 정의는 엄격하지 않았다.[3]컴퓨터 공학은 1965년까지의 다항식 시간의 도입과 함께 엄격한 정의를 제공했다.이와 마찬가지로, 이번과 같은 셈 문제의 경우 정확히 해결할 수 없는 표기법은 1979년에 정의된 #P-강도에 해당해야 한다.

고려해야 할 또 다른 유형의 물리적 시스템은 두 개의 원자를 가진 폴리머인 디머로 구성되어 있다.조광기 모델은 그래프의 조광기 커버 수를 계산한다.[4]고려해야 할 또 다른 물리적 시스템은 얼음의 형태로 HO2 분자의 결합이다.이것은 각 꼭지점에서 가장자리의 방향이 모두 같을 수 없는 지시된 3-규칙 그래프로 모델링할 수 있다.이 모델의 가장자리 방향은 몇 개인가?

1961년 조광기가 포함된 물리적 시스템에 의해 동기 부여된 Kastelyn과[5] Temelley와 Fisher는[6] 독립적으로 m-by-n 사각형의 도미노 기울기 수를 발견했다.이는 m-by-n 격자 그래프의 완벽한 일치 횟수를 계산하는 것과 같다.1967년까지 Kastelyn은 이 결과를 모든 평면 그래프로 일반화했다.[7][8]

알고리즘.

설명

주요 통찰력은 그래프 G의 인접 행렬의 Paffiian에서 0이 아닌 모든 항이 완벽한 일치에 해당한다는 것이다.따라서 Paffian(+ 또는 - )의 모든 항을 정렬하기 위한 G의 방향을 찾을 수 있다면 Pafeian의 절대값은 G의 완벽한 일치 횟수일 뿐이다.FKT 알고리즘은 평면 그래프 G에 대해 그러한 작업을 한다.그것이 발견한 방향을 파피안 방향이라고 한다.

G = (V, E) 인접 행렬 A가 있는 비방향 그래프가 되도록 한다.PM(n)을 정의하여 n개의 요소를 쌍으로 분할한 다음 G의 일치 항목 수는

이것과 밀접하게 관련된 것은 n by n matrix A에 대한 Paffian이다.

여기서 sgn(M)은 순열 M의 기호다. G의 Pappeian 방향은 (1, -1, 0)-접근 행렬 B를 가진 방향 그래프 H로, pf(B) = PerfMatch(G)이다.[9]1967년에 Kastelyn은 평면 그래프가 효율적으로 계산 가능한 Pafeian 방향을 가지고 있다는 것을 증명했다.특히 평면 그래프 G의 경우, H를 G의 평면 내장에서 모든 면에 대해 홀수 수의 가장자리가 시계 방향으로 향하도록 한다.그 다음 H는 G의 파피안 방향이다.

마지막으로, 모든 스큐 대칭 행렬 A에 대해,

여기서 det(A)는 A의 결정 요인이다.이 결과는 케일리 덕분이다.[10]결정요소는 효율적으로 계산할 수 있기 때문에 PerfMatch(G)도 마찬가지다.

개괄적 설명

FKT 알고리즘이 Paffian 방향을 찾는 방법을 보여주는 예.
  1. G의 평면 내장을 계산한다.
  2. 입력 그래프 G의 스패닝 트리 T를1 계산한다.
  3. 또한1 T에 있는 G의 각 가장자리에 임의의 방향을 부여한다.
  4. 평면 임베딩을 사용하여 G의 이중 그래프와 동일한 정점 세트로 (비방향) 그래프 T를2 만드십시오.
  5. G에 있는 해당 면이1 T에 없는 G에 있는 가장자리를 공유하는 경우 두 꼭지점 사이에 T에2 가장자리를 만드십시오(T는2 트리라는 점에 유의).
  6. T의2 각 잎 v에 대해(그것도 루트가 아님):
    1. e를 아직 방향을 잡지 않은 v에 해당하는 얼굴에서 G의 외로운 가장자리가 되게 하라.
    2. 시계 방향의 가장자리 수가 홀수인 방향을 지정하십시오.
    3. T에서2 v를 제거하십시오.
  7. 결정 인자의 제곱근인 G의 (1, -1, 0)-접근 행렬의 Pafeian 절대값을 반환한다.

일반화

또한 마지막 단계에서 인접 행렬에 대한 Tutte 행렬을 사용하여 가중치 있는 완전 일치의 합을 계산할 수 있다.

쿠라토프스키의 정리에는 다음과 같이 되어 있다.

유한 그래프는 K5(정점 5개의 완전 그래프) 또는 K3,3(크기 3의 두 칸에 완전 양분 그래프)에 대한 하위 그래프를 포함하지 않는 경우에만 평면 그래프를 의미한다.

Vijay Vazirani는 K에3,3 대한 서브그래프 동형체를 포함하지 않는 그래프에 FKT 알고리즘을 일반화했다.[11]일반 그래프의 완벽한 일치 횟수를 세는 것은 #P-완전이므로, P의 함수 버전인 FP가 #P와 같지 않으면 입력 그래프의 일부 제한이 필요하다.호소야 지수로 알려진 매치 카운팅도 평면 그래프에서도 #P-완전이다.[12]

적용들

FKT 알고리즘은 매치게이트를 통해 평면 그래프의 홀로그래픽 알고리즘에 광범위하게 사용되어 왔다.[3]예를 들어 위에서 언급한 얼음 모델의 평면 버전을 고려해 보십시오. 기술 이름은 #PL-3-NAE-SAT(여기서 NAE는 "모든 것이 같지 않음"을 의미한다.)Valiant는 매치게이트를 사용하는 이 문제에 대한 다항식 시간 알고리즘을 찾았다.[13]

참조

  1. ^ Hayes, Brian (January–February 2008), "Accidental Algorithms", American Scientist
  2. ^ Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third ed.). Dover Publications. p. 11. ISBN 978-0-486-46271-4.
  3. ^ a b Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2010). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. Las Vegas, NV, USA: IEEE. arXiv:1008.0683. Bibcode:2010arXiv1008.0683C.
  4. ^ Kenyon, Richard; Okounkov, Andrei (2005). "What is a Dimer?" (PDF). AMS. 52 (3): 342–343.
  5. ^ Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice", Physica, 27 (12): 1209–1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5
  6. ^ Temperley, H. N. V.; Fisher, Michael E. (1961). "Dimer problem in statistical mechanics-an exact result". Philosophical Magazine. 6 (68): 1061–1063. doi:10.1080/14786436108243366.
  7. ^ Kasteleyn, P. W. (1963). "Dimer Statistics and Phase Transitions". Journal of Mathematical Physics. 4 (2): 287–293. Bibcode:1963JMP.....4..287K. doi:10.1063/1.1703953.
  8. ^ Kasteleyn, P. W. (1967), "Graph theory and crystal physics", in Harary, F. (ed.), Graph Theory and Theoretical Physics, New York: Academic Press, pp. 43–110
  9. ^ Thomas, Robin (2006). A survey of Pfaffian orientations of graphs (PDF). International Congress of Mathematicians. Vol. III. Zurich: European Mathematical Society. pp. 963–984.
  10. ^ Cayley, Arthur (1847). "Sur les determinants gauches" [On skew determinants]. Crelle's Journal. 38: 93–96.
  11. ^ Vazirani, Vijay V. (1989). "NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems". Information and Computation. 80 (2): 152–164. doi:10.1016/0890-5401(89)90017-5. ISSN 0890-5401.
  12. ^ Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, Bibcode:1987JSP....48..121J, doi:10.1007/BF01010403.
  13. ^ Valiant, Leslie G. (2004). "Holographic Algorithms (Extended Abstract)". Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. FOCS'04. Rome, Italy: IEEE Computer Society. pp. 306–315. doi:10.1109/FOCS.2004.34. ISBN 0-7695-2228-9.

외부 링크

  • 더 많은 역사, 정보, 예시는 드미트리 카메네츠키의 박사 논문 제2장과 제5.3.2절에서 찾을 수 있다.