مسئله تطابق سه‌بعدی

تطابق سه‌بعدی در نظریه گراف تعمیم تطابق دوبخشی (تطابق دوبعدی) به ۳ ابرگراف یک‌شکل است. پیدا کردن بزرگ‌ترین تطابق سه‌بعدی یک مسئله ان‌پی-سخت مشهور در نظریه پیچیدگی محاسباتی است.
تعریف
فرض کنید ، و مجموعه‌های متناهی مجزا باشند و یک زیرمجموعه از
باشد. یعنی شامل ۳ تایی‌های است به طوری که ∋ ، ∋ و ∋ . ⊇ یک تطابق سه‌بعدی است در صورتی که به ازای هر دو سه‌تایی مجزا
∋ ( ) و ∋ ( ) داشته باشیم:
≠ و
مثال
شکل سمت چپ صفحه تطابق‌های سه‌بعدی را نشان می‌دهد. با نقاط قرمز، با نقاط آبی و با نقاط سبز نشان داده شده است. شکل الف مجموعه (نواحی خاکستری) را نشان می‌دهد. شکل ب یک تطابق سه‌بعدی با ۲ = | | را نشان می‌دهد و شکل پ یک تطابق سه‌بعدی با ۳ = | | را نشان می‌دهد.
تطابق که در شکل پ نشان داده‌شده‌است یک تطابق سه‌بعدی بیشینه است، یعنی | | را بیشینه می‌کند. تطابق‌های نشان داده‌شده در شکل‌های ب و پ تطابق‌های سه‌بعدی ماکسیمال هستند، یعنی نمی‌توان با افزودن عضوهای بیش‌تری از آن‌ها را گسترش داد.
مقایسه با مسئله تطابق دو بخشی
یک تطابق دوبعدی را می‌توان به طور کاملا مشابه تعریف کرد. فرض کنید و مجموعه‌های متناهی مجزا باشند و یک زیرمجموعه از × باشد. ⊇ یک تطابق دوبعدی است در صورتی که برای هر دو زوج مجزای
∋ ( ) و ∋ ( ) داشته باشیم: ≠ و ≠ .
در تطابق دوبعدی، مجموعه را می‌توان به صورت مجموعه یال‌ها در یک گراف دوبخشی ( ) = تعبیر کرد؛ هر یال یک راس از را به یک راس از متصل می‌کند و یک تطابق دوبعدی یک تطابق در گراف است، یعنی مجموعه‌ای از یال‌های دوبه‌دو غیرمجاور.
از این رو تطابق‌های سه‌بعدی را می‌توان به صورت تعمیم تطابق به ابرگراف‌ها تعبیر کرد: مجموعه‌های ، و شامل یال‌ها هستند، هر عضو یک ابرگراف است و مجموعه شامل یال‌های دوبه‌دو غیرمجاور است (یال‌هایی که راس مشترک ندارند).
مقایسه با مسئله بسته‌بندی مجموعه
یک تطابق سه‌بعدی حالت خاصی از یک بسته بندی مجموعه است: می‌توانیم هر عضو ( ) از را به عنوان یک زیرمجموعه { از ∪ ∪ تعبیر کنیم؛ پس یک تطابق سه‌بعدی شامل زیرمجموعه‌های دوبه‌دو مجزا است.
مسئله تصمیم
در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله تصمیم زیر است:
با داشتن مجموعه و عدد صحیح ، آیا یک تطابق ⊇ با ≤ | | وجود دارد؟ این مسئله تصمیم ان‌پی-کامل است؛ یکی از ۲۱ مسئله ان‌پی-کامل کارپ است.
این مسئله حتی در حالت خاص | | = | | = | | = هم ان‌پی-کامل است. در این حالت یک تطابق سه‌بعدی نه تنها یک مسئله بسته‌بندی مجموعه است بلکه یک مسئله پوشش دقیق نیز هست: مجموعه هر عضو ، و را دقیقا یک بار پوشش می‌دهد.
مسئله یهینه‌سازی
یک تطابق سه‌بعدی بیشینه یک بزرگترین تطابق سه‌بعدی است. در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله بهینه‌سازی زیر است:
با داشتن مجموعه ، یک تطابق سه‌بعدی ⊇ که | | را بیشینه می‌کند پیدا کنید.
از آنجا که مسئله تصمیمی که در بالا آورده‌شد ان‌پی-سخت است، این مسئله بهینه‌سازی ان‌پی-کامل می‌باشد و به نظر می‌آید که الگوریتمی چندجمله‌ای برای پیدا کردن یک تطابق سه‌بعدی بیشینه وجود ندارد. به هر حال، الگوریتم‌های چندجمله‌ای بهینه‌ای برای پیداکردن یک تطابق دوبخشی بیشینه (تطابق دوبعدی بیشینه) وجود دارند، برای مثال، الگوریتم هاپکرافت-کارپ.
الگوریتم‌های تقریبی
این مسئله APX-کامل است، یعنی به سختی می‌توان آن را در حدود یک عدد ثابت تقریب زد. برای هر عدد مثبت ثابت >0، یک الگوریتم چندجمله‌ای ( + ۳/۲)-تقریب برای تطابق سه‌بعدی وجود دارد.
یک الگوریتم خیلی ساده چندجمله‌ای ۳-تقریب برای تطابق سه‌بعدی وجود دارد: یک تطابق سه‌بعدی ماکسیمال بیابید. همان‌گونه که یک تطابق ماکسیمال در حدود عامل ۲ یک تطابق بیشینه است، یک تطابق سه‌بعدی ماکسیمال نیز در حدود عامل ۳ یک تطابق سه‌بعدی بیشینه است.