Dense subgraph
গ্রাফ তত্ত্ব এবং কম্পিউটার বিজ্ঞানে, একটি ঘন উপগ্রাফ হল একটি উপগ্রাফ যার প্রতি শীর্ষে অনেক প্রান্ত থাকে। এটি নিম্নরূপ আনুষ্ঠানিক করা হয়েছেঃ একটি অনির্দিষ্ট গ্রাফ হতে দিন এবং এর একটি উপগ্রাফ হতে দিন। তারপর এর ঘনত্বকে সংজ্ঞায়িত করা হয়ঃ সবচেয়ে ঘন সাবগ্রাফ সমস্যা হল সর্বাধিক ঘনত্বের একটি সাবগ্রাফ খুঁজে বের করা। একটি গ্রাফের সর্বাধিক ঘন সাবগ্রাফের ঘনত্বকে কখনও কখনও এর সাবগ্রাফ ঘনত্ব হিসাবে উল্লেখ করা হয়। 1984 সালে, অ্যান্ড্রু ভি গোল্ডবার্গ একটি সর্বাধিক প্রবাহ কৌশল ব্যবহার করে সর্বাধিক ঘনত্বের সাবগ্রাফ খুঁজে বের করার জন্য একটি বহুপদী সময় অ্যালগরিদম তৈরি করেছিলেন। 1989 সালে গ্যালো, গ্রিগোরিয়াডিস এবং টারজান দ্বারা সময়মতো চলার জন্য এটি উন্নত করা হয়েছে। 2000 সালে চারিকর সর্বোত্তম সমাধান খুঁজে বের করার জন্য একটি সহজ এলপি দিয়েছিলেন। সাবগ্রাফ ঘনত্ব আরবোরিসিটি এবং গ্রাফ অবক্ষয়ের সম্পর্কিত ধারণার সাথে অ্যাসিম্পটোটিক। ঘনতম সাবগ্রাফ সমস্যাটির অনেক বৈচিত্র রয়েছে। এর মধ্যে একটি হল ঘনতম সাবগ্রাফ সমস্যা, যেখানে উদ্দেশ্য হল ঠিক শীর্ষে সর্বাধিক ঘনত্বের সাবগ্রাফ খুঁজে বের করা। এই সমস্যাটি চক্রের সমস্যাটিকে সাধারণীকরণ করে এবং এইভাবে সাধারণ গ্রাফগুলিতে এনপি-হার্ড হয়। একটি বহুপদী অ্যালগরিদম রয়েছে যা প্রতিটির জন্য অনুপাতের মধ্যে ঘনতম সাবগ্রাফকে আনুমানিক করে, যদিও এটি বহুপদী সময়ে একটি-অনুমোদন স্বীকার করে না যদি না সূচকীয় সময় অনুমানটি মিথ্যা হয়। একটি দুর্বল ধারণার অধীনে যে, সমস্যার জন্য কোনও পিটিএএস বিদ্যমান নেই। দ্বিদলীয় গ্রাফ এবং কর্ডাল গ্রাফগুলিতে সমস্যাটি এনপি-শক্ত থাকে তবে গাছ এবং বিভক্ত গ্রাফের জন্য বহুপদী। (যথাযথ) ব্যবধান গ্রাফ এবং সমতলীয় গ্রাফগুলিতে সমস্যাটি এন. পি-হার্ড বা বহুপদী কিনা তা উন্মুক্ত; তবে, সমতলীয় গ্রাফগুলিতে যে সমস্যার একটি বৈচিত্র্য যেখানে উপগ্রাফটি সংযুক্ত করা প্রয়োজন তা এন. পি-হার্ড। সর্বাধিক সাবগ্রাফ ঘনত্ব সর্বাধিক সমস্যার ঘনত্বের উদ্দেশ্য হল সর্বাধিক শীর্ষে সর্বাধিক ঘনত্বের সাবগ্রাফ খুঁজে বের করা। অ্যান্ডারসন এবং চেল্লাপিলা দেখিয়েছেন যে এই সমস্যার জন্য যদি কোনও-অনুমোদন বিদ্যমান থাকে তবে এটি ঘনতম সাবগ্রাফ সমস্যার জন্য একটি-অনুমোদনের দিকে পরিচালিত করবে। সবচেয়ে ঘনতম অন্তত সাবগ্রাফ সবচেয়ে ঘনতম সমস্যাটিকে বেশিরভাগ সাবগ্রাফ সমস্যার মতো একইভাবে সংজ্ঞায়িত করা হয়। সমস্যাটি এনপি-সম্পূর্ণ, তবে পলিনোমিয়াল সময়ে 2-অ্যাপ্রোক্সিমেশন স্বীকার করে। উপরন্তু, কিছু প্রমাণ রয়েছে যে এই আনুমানিক অ্যালগরিদমটি মূলত সর্বোত্তম সম্ভাব্যঃ ছোট সেট সম্প্রসারণ অনুমান (অনন্য গেম অনুমানের সাথে ঘনিষ্ঠভাবে সম্পর্কিত একটি গণনামূলক জটিলতা অনুমান) ধরে নিলে, প্রতিটি ধ্রুবকের জন্য ফ্যাক্টরের মধ্যে সমস্যাটি আনুমানিকভাবে অনুমান করা এনপি-কঠিন। ------------------------------------------------------------------------------------------------------------------------------------- - ঘনতম সাবগ্রাফ সমস্যার এই পরিবর্তনের লক্ষ্য হল প্ররোচিত চক্রের গড় সংখ্যা সর্বাধিক করা, যেখানে-ক্লিকের সেট দ্বারা প্ররোচিত হয়। লক্ষ্য করুন যে ঘনতম সাবগ্রাফ সমস্যাটি একটি বিশেষ কেস হিসাবে প্রাপ্ত হয়। এই সাধারণীকরণ বড় আকারের বাস্তব-বিশ্বের নেটওয়ার্কগুলি থেকে বড় কাছাকাছি-ক্লিকগুলি বের করার জন্য একটি অভিজ্ঞতাগতভাবে সফল পলি-টাইম পদ্ধতি প্রদান করে। স্থানীয়ভাবে সবচেয়ে ঘন সাবগ্রাফ কিন এবং অন্যান্য। একটি গ্রাফে টপ-কে স্থানীয়ভাবে ঘনতম সাবগ্রাফ আবিষ্কারের সমস্যাটি প্রবর্তন করা হয়েছে, যার প্রত্যেকটি গ্রাফে তার স্থানীয় অঞ্চলে সর্বোচ্চ ঘনত্ব অর্জন করেঃ এটি একই বা বৃহত্তর ঘনত্ব সহ কোনও সুপারগ্রাফে অন্তর্ভুক্ত নয়, বা এটিতে ঘনত্ব সহ সাবগ্রাফও নেই যা স্থানীয় ঘনতম সাবগ্রাফের বাকি অংশের সাথে আলগাভাবে সংযুক্ত। লক্ষ্য করুন যে ঘনতম সাবগ্রাফ সমস্যাটি একটি বিশেষ ক্ষেত্রে প্রাপ্ত হয়। একটি গ্রাফে স্থানীয়ভাবে ঘনতম সাবগ্রাফগুলির সেট বহুপদী সময়ে গণনা করা যেতে পারে। তথ্যসূত্র আরও পড়া। । । । । গ্রাফ তত্ত্ব