Pairwise compatibility graph
গ্রাফ তত্ত্বে, একটি গ্রাফ একটি পেয়ারওয়াইজ কম্প্যাটিবিলিটি গ্রাফ (পিসিজি) হয় যদি একটি ট্রি এবং দুটি অ-নেতিবাচক বাস্তব সংখ্যা বিদ্যমান থাকে যাতে প্রতিটি নোডের একটি লিফ নোডের সাথে এক-থেকে-এক ম্যাপিং থাকে যাতে দুটি নোড থাকে এবং যদি এবং শুধুমাত্র যদি এবং এর মধ্যে দূরত্ব ব্যবধানের মধ্যে থাকে। পি. সি. জি-র উপশ্রেণীগুলির মধ্যে রয়েছে সর্বাধিক সাতটি শীর্ষ, চক্র, বন, সম্পূর্ণ গ্রাফ, ব্যবধান গ্রাফ এবং মই গ্রাফ। তবে, আটটি শীর্ষ সহ একটি গ্রাফ রয়েছে যা পিসিজি নয় বলে জানা যায়। ফাইলোজেনেটিক্সের সাথে সম্পর্ক জোড়া সামঞ্জস্য গ্রাফ প্রথম পল কেয়ার্নি, জে. ইয়ান মুনরো এবং ডেরেক ফিলিপস দ্বারা ফাইলোজেনি পুনর্গঠনের প্রসঙ্গে প্রবর্তিত হয়েছিল। একটি ফাইলোজেনেটিক গাছ থেকে নমুনা নেওয়ার সময়, প্রদত্ত দৈর্ঘ্যের মধ্যে পথের দূরত্বের নোডগুলি খুঁজে বের করার কাজটি সংশ্লিষ্ট পিসিজিতে একটি চক্র খুঁজে বের করার সমতুল্য। জটিলতা একটি গ্রাফকে পি. সি. জি হিসাবে স্বীকৃতি দেওয়ার গণনামূলক জটিলতা 2020 সাল পর্যন্ত অজানা। যাইহোক, একটি গ্রাফ এবং একটি নন-এজ সম্পর্কের একটি নির্বাচন খুঁজে বের করার সম্পর্কিত সমস্যা একটি পিসিজি যা একটি সাবগ্রাফ হিসাবে ধারণ করে এবং যার কোনও প্রান্ত নেই তা এনপি-হার্ড হিসাবে পরিচিত। একটি গাছে নোড খুঁজে বের করার কাজ যার পথের দূরত্ব এবং এর মধ্যে অবস্থিত যা বহুপদী সময়ে সমাধানযোগ্য বলে জানা যায়। অতএব, যদি পলিনোমিয়াল সময়ে একটি পিসিজি থেকে গাছটি পুনরুদ্ধার করা যায়, তবে পিসিজিগুলির উপর ক্লিক সমস্যাটিও পলিনোমিয়াল হবে। 2020 সালের হিসাবে, এই জটিলতাগুলির কোনওটিই জানা যায় না। তথ্যসূত্র গ্রাফ পরিবার গণনামূলক ফাইলোজেনেটিক্স