الگوریتم FKT

الگوریتم FKT که نام آن از ابتدای نام‌های Fisher, Kasteleyn و Temperley گرفته شده‌است، الگوریتمی است که به شمارش تعداد تطابق کامل در یک گراف مسطح با زمان چندجمله ای می‌پردازد. این کار برای گراف‌های عمومی به صورت P-کامل می‌باشد. شمارش تعداد تطابق، حتی برای گراف‌های مسطح نیز به صورت P-کامل می‌باشد. ایده اصلی، تبدیل مسئله به یک پردازش از ماتریس متقارن مورب که از جاسازی مسطح گراف به دست آمده است می‌باشد. بدین ترتیب این ماتریس به سرعت از الگوریتم استاندارد دترمینان محاسبه می‌گردد.

تاریخچه

مسئله شمارش تعداد تطابق کامل مسطح، ریشه در مکانیک آماری و شیمی دارد، در آنجا سؤال اصلی این بوده‌است که آیا مولکول‌های دو اتمی که بر روی یک سطح جذب می‌شوند و تشکیل یک لایه می‌دهند به چند طریق می‌توان آن‌ها را مرتب نمود؟^[۱] تابع پارتیشن یک کمیت بسیار مهم می‌باشد که ویژگی‌های آماری یک سیستم در حال تعادل را رمز می‌کند و می‌توان از آن برای حل مسئله پیشین استفاده نمود. هرچند که تلاش برای محاسبه تابع پارتیشن از تعریف آن، چندان عملی نیست؛ بنابراین برای حل دقیق یک سیستم فیزیکی باید شکل مشابهی از تابع پارتیشن را برای آن سیستم فیزیکی خاص پیدا کنیم که محاسبه آن به اندازه کافی ساده باشد.^[۲] در اوایل ۱۹۶۰، تعریف دقیقاً قابل حل، چندان ملموس نبود.^[۳] در ۱۹۶۵، علم کامپیوتر یک تعریف جدی با معرفی زمان چندجمله‌ای ارائه نمود. به‌طور مشابه در سال ۱۹۷۹، تعریف نه چندان دقیق قابل حل که به مسائل P-سختی برمی گردد، ارائه شد. نوع دیگری از سیستم فیزیکی که قابل بررسی است ترکیبی از دیمرها می‌باشد. دیمرها، پلیمری با دو اتم می‌باشند. مدل دیمر، تعداد پوشش‌های دیمر از یک گراف را می‌شمارد. یک سیستم فیزیکی قابل بررسی دیگر، اتصال مولکول‌های آب H₂O که تشکیل یخ می‌دهند می‌باشد . این سیستم را می‌توان به عنوان یک گراف جهت دار منظم ۳ تایی که جهت یال‌ها در هر راس آن نمی‌تواند یکسان باشد، مدل نمود. سؤال این است که چه تعداد جهت یال در این گراف می‌تواند در این گراف وجود داشته باشد؟ با انگیزه سیستم‌های فیزیکی که دیمرها هم شامل آن‌ها می‌شود در سال ۱۹۶۱، Kasteleyn, Temperley و Fisher هر کدام به‌طور مستقل تعداد کاشی کاری‌های دومینو را برای یک مستطیل m در n پیدا کردند. این فرمول برابر با شمارش تعداد تطابق کامل برای یک یک گراف شبکه m در n می‌باشد. در ۱۹۶۷، Kasteleyn این نتیجه را برای تمام گراف‌های مسطح گسترش داد.

الگوریتم

شرح

دید کلی این است که هر جمله غیر صفر در Pfaffian از ماتریس مجاورت گراف G با یک تطابق کامل مرتبط است؛ بنابراین اگر جهت‌گیری ای از G پیدا شود که مطابق تمام علائم جملات موجود در Pfaffian باشد (مثبت یا منفی بودن فرقی نمی‌کند)، آنگاه می‌توان گفت قدرمطلق Pfaffian نشان دهنده تعداد تطابق کامل گراف G می‌باشد. الگوریتم FKT این کار را برای یک گراف مسطح G انجام می‌دهد. فرض کنیم (G = (V, E یک گراف بدون جهت با ماتریس مجاورت A باشد. (PM(n را به عنوان مجموعه ای از پارتیشن‌های عناصر n به صورت جفتی تعریف می‌کنیم، سپس تعداد تطابق کامل در G به صورت زیر بدست می‌آید:

$\operatorname {PerfMatch} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.$

فرمول مرتبط به این موضوع، فرمول Pfaffian برای هر ماتریس n در n مانند A می‌باشد:

$\operatorname {pf} (A)=\sum _{M\in PM(n)}\operatorname {sgn} (M)\prod _{(i,j)\in M}A_{ij},$

در نهایت، برای هر ماتریس متقارن مورب A داریم:

$\operatorname {pf} (A)^{2}=\det(A),$

که در آن (det(A نشان دهنده دترمینان A می‌باشد. این نتجه از زحمات Cayley می‌باشد. از آنجا که دترمینان به راحتی قابل محاسبه است، فرمول بدست آمده هم قابل محاسبه خواهد بود.^[۴]

توضیحات سطح بالا

مثالی برای روش پیدا کردن جهات Pfaffian با استفاده از الگوریتم FKT

محاسبه مسطح تعبیه شده G
محاسبه درخت پوشای T1 از گراف ورودی G
به هر یال از G که از T1 نیز می‌باشد یک جهت اختیاری تخصیص می‌دهیم
ساخت یک گراف بدون جهت به نام T2 با مجموعه راس‌های گراف همزاد G با استفاده از مسطح تعبیه شده
ساخت یک یال در T2 که بین دو راس آن در گراف متناظر آن در G یالی اینچنین وجود ندارد (دقت داشته باشید که T2 یک درخت می‌باشد)
برای هر یال v در T2 (که ریشه نیست):
1. فرض کنید e تنها یال G می‌باشد در مقابل v که هنوز جهتی به آن اختصاص داده نشده‌است
2. به e یک جهت اختصاص دهید به گونه ای که تعداد یال‌هایی که جهت آن‌ها پاد ساعتگرد می‌باشد، فرد گردد.
3. یال v را از T2 حذف کنید
قدر مطلق Pfaffian از ماتریس مجاورت (۰و۱-و۱) گراف G را باز گردان، که برابر است با قدر مطلق توان دوم دترمینان.

تعمیم

مجموع تطابق کامل وزن دار را نیز می‌توان با استفاده از ماتریس Tutte برای ماتریس مجاورت در گام نهایی انجام داد. تئوری Kuratowski اثبات می‌کند که: یک گراف کامل، مسطح است اگر و فقط اگر شامل هیچ زیر گرافی که با گراف کامل ۵ تایی یا با گراف جفت کامل سه تایی (گرافی جفت کامل با دو بخش با اندازه 3) homeomorphic نباشد.^[۵] Vijay Vazirani الگوریتم FKT را برای گراف‌هایی که شامل زیر گراف جفت کامل سه تایی نمی‌شوند گسترش داده است. از آنجا که شمارش تعداد تطابق کامل در یک گراف عمومی P-کامل می‌باشد، محدودیت‌هایی بر روی گراف ورودی باید اعمال شود مگر اینکه FP (نسخه ای تابعی از P) برابر با P باشد. شمارش تطابق‌ها، که با نام اندیس Hosoya شناخته می‌شود نیز حتی برای گراف‌های مسطح هم، یک مسئله P-کامل می‌باشد.^[۶]

کاربردها

الگوریتم FKT کاربرد زیادی در الگوریتم‌های هولوگرافیک بر روی گراف‌های مسطح در میان دروازه‌های انطباق دارد. برای مثال، نسخه مسطح از مدل یخ آورده شده در بالا را در نظر بگیرید که نام تکنیکی آن PL-3-NAE-SAT می‌باشد (که NAE در آن به معنای همه برابر نیستند می‌باشد). Valiant یک الگوریتم زمان چندجمله ای برای این مسئله پیدا نموده است که از دروازه‌های انطباق استفاده می‌کند.^[۷]

منابع و مراجع

↑ Hayes, Brian (January–February 2008), "Accidental Algorithms", American Scientist
↑ Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third ed.). Dover Publications. p. 11. ISBN 978-0-486-46271-4. Archived from the original on 20 March 2012. Retrieved 9 June 2015.
↑ 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. {{cite conference}}: External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)
↑ Cayley, Arthur (1847). "Sur les determinants gauches" [On skew determinants]. Crelle's Journal. 38: 93–96.
↑ Vazirani, Vijay V. (1989). "NC algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems". Information and Computation. 80 (2): 152–164. doi:10.1016/0890-5401(89)90017-5. ISSN 0890-5401.
↑ Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, doi:10.1007/BF01010403.
↑ 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. {{cite conference}}: |access-date= requires |url= (help); |archive-url= requires |url= (help); External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)

لینک‌های مرتبط

Presentation by Ashley Montanaro about the FKT algorithm
More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis

[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. Archived from the original on 20 March 2012. Retrieved 9 June 2015.

[CLX-3] 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. {{cite conference}}: External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)

[4] Cayley, Arthur (1847). "Sur les determinants gauches" [On skew determinants]. Crelle's Journal. 38: 93–96.

[5] Vazirani, Vijay V. (1989). "NC algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems". Information and Computation. 80 (2): 152–164. doi:10.1016/0890-5401(89)90017-5. ISSN 0890-5401.

[6] Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, doi:10.1007/BF01010403.

[7] 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. {{cite conference}}: |access-date= requires |url= (help); |archive-url= requires |url= (help); External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]