Twin-width
একটি অনির্দিষ্ট গ্রাফের যমজ-প্রস্থ হল গ্রাফের সাথে যুক্ত একটি প্রাকৃতিক সংখ্যা, যা গ্রাফ অ্যালগরিদমের প্যারামিটারাইজড জটিলতা অধ্যয়ন করতে ব্যবহৃত হয়। স্বজ্ঞাতভাবে, এটি পরিমাপ করে যে গ্রাফটি একটি গ্রাফের সাথে কতটা মিল, এক ধরনের গ্রাফ যা বারবার যমজ, একই প্রতিবেশীযুক্ত শীর্ষগুলি একত্রিত করে একক শীর্ষে হ্রাস করা যেতে পারে। যমজ-প্রস্থকে পুনরাবৃত্ত সংযুক্তির ক্রম থেকে সংজ্ঞায়িত করা হয় যেখানে শীর্ষগুলি যমজ হওয়ার প্রয়োজন হয় না, তবে প্রতিবেশীদের প্রায় সমান সেট থাকে। সংজ্ঞা দ্বৈত-প্রস্থ সীমাবদ্ধ সহজ অনির্দিষ্ট গ্রাফের জন্য সংজ্ঞায়িত করা হয়। এগুলির শীর্ষগুলির একটি সীমাবদ্ধ সেট রয়েছে এবং প্রান্তগুলির একটি সেট রয়েছে যা শীর্ষগুলির ক্রমহীন জোড়া। যে কোনও শীর্ষের খোলা প্রতিবেশী হল অন্যান্য শীর্ষগুলির সেট যা এটি গ্রাফের প্রান্তে যুক্ত করা হয়; বদ্ধ প্রতিবেশীটি খোলা প্রতিবেশী থেকে শীর্ষকে অন্তর্ভুক্ত করে গঠিত হয়। দুটি শীর্ষগুলি সত্য যমজ হয় যখন তাদের একই বদ্ধ প্রতিবেশী থাকে এবং মিথ্যা যমজ যখন তাদের একই খোলা প্রতিবেশী থাকে; আরও সাধারণভাবে, সত্য যমজ এবং মিথ্যা যমজ উভয়কেই যোগ্যতা ছাড়াই যমজ বলা যেতে পারে। গ্রাফগুলির অনেক সমতুল্য সংজ্ঞা রয়েছে, তবে এগুলির মধ্যে একটি হল যে এগুলি এমন গ্রাফ যা যে কোনও দুটি যমজ শীর্ষস্থান বারবার খুঁজে বের করার এবং তাদের একক শীর্ষে একীভূত করার প্রক্রিয়া দ্বারা একক শীর্ষে হ্রাস করা যেতে পারে। একটি গ্রাফের জন্য, এই হ্রাস প্রক্রিয়াটি সর্বদা সফল হবে, প্রতিটি ধাপে যমজদের একত্রিত করার জন্য যে পছন্দই হোক না কেন। একটি গ্রাফের জন্য যা একটি গ্রাফ নয়, এটি সর্বদা একটি উপগ্রাফ-এ আটকে থাকবে যার দুটি শীর্ষের বেশি রয়েছে যার কোনও যমজ নেই। যমজ-প্রস্থের সংজ্ঞাটি এই হ্রাস প্রক্রিয়াটিকে অনুকরণ করে। একটি সংকোচন ক্রম, এই প্রসঙ্গে, প্রদত্ত গ্রাফ দিয়ে শুরু হওয়া ধাপগুলির একটি ক্রম, যেখানে প্রতিটি ধাপ এক জোড়া শীর্ষকে একটি একক শীর্ষ দ্বারা প্রতিস্থাপন করে। এটি লাল এবং কালো রঙের প্রান্ত সহ গ্রাফের একটি ক্রম তৈরি করে; প্রদত্ত গ্রাফে, সমস্ত প্রান্ত কালো বলে ধরে নেওয়া হয়। যখন দুটি শীর্ষকে একটি একক শীর্ষ দ্বারা প্রতিস্থাপিত করা হয়, তখন নতুন শীর্ষের প্রতিবেশী হল প্রতিস্থাপিত শীর্ষগুলির আশেপাশের সংযোগ। এই নতুন পাড়ায়, উভয় শীর্ষের আশেপাশের কালো প্রান্ত থেকে আসা একটি প্রান্ত কালো থাকে; অন্যান্য সমস্ত প্রান্ত লাল রঙের হয়। একটি সংকোচন ক্রমকে বলা হয়-ক্রম যদি, ক্রম জুড়ে, প্রতিটি শীর্ষ সর্বাধিক লাল প্রান্তে স্পর্শ করে। একটি গ্রাফের যমজ-প্রস্থ হল সবচেয়ে ছোট মান যার জন্য এটির একটি-ক্রম রয়েছে। একটি ঘন গ্রাফের এখনও দ্বৈত-প্রস্থ সীমাবদ্ধ থাকতে পারে; উদাহরণস্বরূপ, গ্রাফগুলিতে সমস্ত সম্পূর্ণ গ্রাফ অন্তর্ভুক্ত থাকে। দ্বৈত-প্রস্থের একটি বৈচিত্র্য, বিরল দ্বৈত-প্রস্থ, পৃথক গ্রাফের পরিবর্তে গ্রাফের পরিবারের ক্ষেত্রে প্রযোজ্য। গ্রাফের একটি পরিবারের জন্য যা প্ররোচিত উপগ্রাফ গ্রহণের অধীনে বন্ধ থাকে এবং দ্বৈত-প্রস্থ সীমাবদ্ধ থাকে, নিম্নলিখিত বৈশিষ্ট্যগুলি সমতুল্যঃ পরিবারের গ্রাফগুলি বিরল, যার অর্থ তাদের শীর্ষগুলির সংখ্যার রৈখিক ফাংশন দ্বারা আবদ্ধ বেশ কয়েকটি প্রান্ত রয়েছে। এই পরিবারে সমস্ত সম্পূর্ণ দ্বিদলীয় গ্রাফ অন্তর্ভুক্ত নয়। প্রদত্ত পরিবারের গ্রাফের সমস্ত উপ-গ্রাফের পরিবারে দ্বৈত-প্রস্থ রয়েছে। পরিবারটির সীমাবদ্ধ সম্প্রসারণ রয়েছে, যার অর্থ হল এর সমস্ত অগভীর অপ্রাপ্তবয়স্করা বিরল। এই ধরনের একটি পরিবার বিরল যমজ-প্রস্থের সীমাবদ্ধ বলে মনে করা হয়। দ্বৈত-প্রস্থের ধারণাটি গ্রাফ থেকে বিভিন্ন সম্পূর্ণ ক্রমযুক্ত কাঠামোতে (তাদের শীর্ষে মোট ক্রমযুক্ত গ্রাফ সহ) সাধারণীকরণ করা যেতে পারে এবং ক্রমহীন গ্রাফের তুলনায় ক্রমযুক্ত কাঠামোর জন্য অনেক উপায়ে সহজ। সীমাবদ্ধ মাত্রার তুলনায় বিভিন্ন প্রয়োজনীয়তার সাথে সংকোচন ক্রম ব্যবহার করে গ্রাফ প্রস্থের অন্যান্য ধারণার জন্য সমতুল্য সংজ্ঞা প্রণয়ন করাও সম্ভব। আবদ্ধ যমজ-প্রস্থ গ্রাফের গ্রাফগুলিতে যমজ-প্রস্থ শূন্য থাকে। গ্রাফের হ্রাস প্রক্রিয়ায়, কোনও লাল প্রান্ত থাকবে নাঃ যখন দুটি শীর্ষ একত্রিত হয়, তখন তাদের আশেপাশের অঞ্চলগুলি সমান হয়, তাই দুটি পাড়ার মধ্যে কেবল একটি থেকে লাল রঙের কোনও প্রান্ত আসে না। অন্য যে কোনও গ্রাফে, যে কোনও সংকোচনের ক্রম কিছু লাল প্রান্ত তৈরি করবে এবং যমজ-প্রস্থ শূন্যের চেয়ে বেশি হবে। সর্বাধিক তিনটি শীর্ষ সহ পাথ গ্রাফগুলি হল গ্রাফ, তবে প্রতিটি বড় পাথ গ্রাফের দুটি-প্রস্থ রয়েছে। একটি সংকোচন ক্রমের জন্য যা বারবার পথের শেষ দুটি প্রান্তকে একত্রিত করে, শুধুমাত্র একক সংযুক্ত শীর্ষে প্রান্তের ঘটনা লাল হবে, তাই এটি একটি 1-ক্রম। গাছগুলির সর্বাধিক দুটি প্রস্থ থাকে এবং কিছু গাছের জন্য এটি আঁটসাঁট। যে কোনও গাছের জন্য একটি 2-সংকোচন ক্রম খুঁজে পাওয়া যেতে পারে একটি শিকড় বেছে নেওয়ার মাধ্যমে, এবং তারপরে বারবার দুটি পাতাকে একত্রিত করে যার একই প্যারেন্ট রয়েছে বা, যদি এটি সম্ভব না হয়, গভীরতম পাতাটিকে তার প্যারেন্টে একত্রিত করে। শুধুমাত্র লাল প্রান্তগুলি তাদের পিতামাতার সাথে পাতাগুলিকে সংযুক্ত করে এবং যখন একই পিতামাতার দুটি থাকে তখন সেগুলি লাল ডিগ্রি সর্বাধিক দুটিতে রেখে একত্রিত করা যেতে পারে। আরও সাধারণভাবে, গ্রাফের নিম্নলিখিত শ্রেণীগুলির দ্বৈত-প্রস্থ রয়েছে এবং বহুপদী সময়ে তাদের জন্য আবদ্ধ প্রস্থের একটি সংকোচন ক্রম পাওয়া যায়ঃ আবদ্ধ চক্র-প্রস্থ বা আবদ্ধ র্যাঙ্ক-প্রস্থের প্রতিটি গ্রাফের দ্বৈত-প্রস্থও রয়েছে। যমজ-প্রস্থটি চক্র-প্রস্থের মধ্যে সর্বাধিক সূচকীয় এবং র্যাঙ্ক-প্রস্থের মধ্যে সর্বাধিক দ্বিগুণ সূচকীয়। এই গ্রাফগুলির মধ্যে রয়েছে, উদাহরণস্বরূপ, দূরত্ব-বংশগত গ্রাফ, এর সীমাবদ্ধ মানগুলির জন্য-পাতার ক্ষমতা এবং সীমাবদ্ধ ত্রি-প্রস্থের গ্রাফ। উদাসীনতা গ্রাফের (সমতুল্য, একক ব্যবধান গ্রাফ বা সঠিক ব্যবধান গ্রাফ) সর্বাধিক দুটি প্রস্থ থাকে। একক ডিস্ক গ্রাফগুলি একক ডিস্কের সেট থেকে সংজ্ঞায়িত করা হয় যা সমতলের প্রতিটি বিন্দুকে সীমাবদ্ধ সংখ্যক বার আবদ্ধ করে। উচ্চ মাত্রায় একক বল গ্রাফের ক্ষেত্রেও একই কথা প্রযোজ্য। একটি নিষিদ্ধ ক্রমবিন্যাস প্যাটার্ন সহ ক্রমবিন্যাস থেকে আসা ক্রমবিন্যাস গ্রাফগুলি দ্বৈত-প্রস্থকে সীমাবদ্ধ করেছে। এটি নিষিদ্ধ নিদর্শনগুলির সাথে বিন্যাসের উপর অ্যালগরিদমিক সমস্যাগুলিতে দ্বৈত-প্রস্থ প্রয়োগ করার অনুমতি দেয়। নিষিদ্ধ অপ্রাপ্তবয়স্কদের দ্বারা সংজ্ঞায়িত গ্রাফের প্রতিটি পরিবারের দ্বৈত-প্রস্থ রয়েছে। উদাহরণস্বরূপ, ওয়াগনারের উপপাদ্য অনুসারে, সমতলীয় গ্রাফের জন্য নিষিদ্ধ অপ্রধান দুটি গ্রাফ এবং তাই সমতলীয় গ্রাফগুলি যমজ-প্রস্থ সীমাবদ্ধ করে। বাউন্ডেড স্ট্যাক নম্বর বা বাউন্ডেড কিউ নম্বরের প্রতিটি গ্রাফেও বাইন্ডেড টুইন-উইথ রয়েছে। সীমাবদ্ধ বিরল যমজ-প্রস্থের গ্রাফের পরিবার রয়েছে যার সীমাবদ্ধ স্ট্যাক নম্বর নেই, তবে সারি নম্বরের জন্য সংশ্লিষ্ট প্রশ্নটি খোলা থাকে। আবদ্ধ যমজ-প্রস্থের যে কোনও দুটি গ্রাফের শক্তিশালী গুণফল, যার মধ্যে একটির সীমাবদ্ধ ডিগ্রি রয়েছে, আবার যমজ-প্রস্থকে আবদ্ধ করেছে। এটি গ্রাফের শ্রেণীগুলির সীমাবদ্ধ দ্বৈত-প্রস্থ প্রমাণ করতে ব্যবহার করা যেতে পারে যার পথ এবং সীমাবদ্ধ-ত্রি-প্রস্থ গ্রাফের শক্তিশালী পণ্যগুলিতে পচন রয়েছে, যেমন-সমতলীয় গ্রাফ। গ্রাফের অভিধানগত পণ্যের জন্য, যমজ-প্রস্থ ঠিক দুটি ফ্যাক্টর গ্রাফের প্রস্থের সর্বোচ্চ। দ্বৈত-প্রস্থ অন্যান্য বেশ কয়েকটি স্ট্যান্ডার্ড গ্রাফ পণ্যের অধীনেও ভাল আচরণ করে, তবে গ্রাফের মডুলার পণ্য নয়। আবদ্ধ যমজ-প্রস্থের গ্রাফের প্রতিটি বংশগত পরিবারে, তার গ্রাফের শীর্ষগুলির জন্য মোট ক্রমের একটি পরিবার খুঁজে পাওয়া সম্ভব যাতে একটি প্ররোচিত উপ-গ্রাফের উপর উত্তরাধিকারসূত্রে প্রাপ্ত ক্রমটিও পরিবারে একটি ক্রম হয় এবং যাতে এই ক্রমগুলির ক্ষেত্রে পরিবারটি ছোট হয়। এর অর্থ হল, শীর্ষে মোট ক্রমের জন্য, সেই ক্রমের সাথে সামঞ্জস্যপূর্ণ পরিবারে গ্রাফের সংখ্যা সর্বাধিক এককভাবে সূচকীয়। বিপরীতভাবে, এই অর্থে ছোট ক্রমযুক্ত গ্রাফের প্রতিটি বংশগত পরিবারে দ্বৈত-প্রস্থ রয়েছে। এটি মূলত অনুমান করা হয়েছিল যে লেবেলযুক্ত গ্রাফের প্রতিটি বংশগত পরিবার যা ছোট, এই অর্থে যে গ্রাফের সংখ্যা সর্বাধিক একটি একক সূচকীয় ফ্যাক্টর সময়, দ্বৈত-প্রস্থকে সীমাবদ্ধ করেছে। যাইহোক, এই অনুমানটি একটি অসীম কেলি গ্রাফের প্ররোচিত সাবগ্রাফগুলির একটি পরিবার ব্যবহার করে অস্বীকার করা হয়েছিল যা লেবেলযুক্ত গ্রাফ হিসাবে ছোট তবে দ্বৈত-প্রস্থ সীমাবদ্ধ নয়। গ্রাফের নিম্নলিখিত পরিবারগুলির মধ্যে সীমাহীন যমজ-প্রস্থের গ্রাফ রয়েছেঃ সীমাবদ্ধ মাত্রার গ্রাফ। ব্যবধান গ্রাফ। একক ডিস্ক গ্রাফ। এই প্রতিটি ক্ষেত্রে, ফলাফলটি একটি গণনা যুক্তি দ্বারা অনুসরণ করা হয়ঃ প্রদত্ত ধরনের আরও বেশি গ্রাফ রয়েছে যা আবদ্ধ যমজ-প্রস্থের গ্রাফ হতে পারে। বৈশিষ্ট্য যদি একটি গ্রাফের দ্বৈত-প্রস্থ সীমাবদ্ধ থাকে, তবে সংকোচনের একটি বহুমুখী গাছ খুঁজে পাওয়া সম্ভব। এটি সংকোচন ক্রমের একটি বড় পরিবার, যার সবগুলিই কিছু (বৃহত্তর) সীমাবদ্ধ প্রস্থ, যাতে প্রতিটি ক্রমের প্রতিটি ধাপে রৈখিকভাবে অনেকগুলি বিচ্ছিন্ন জোড়া শীর্ষ থাকে যার প্রতিটি ক্রমের পরবর্তী ধাপে সংকুচিত হতে পারে। এর থেকে বোঝা যায় যে প্রদত্ত শীর্ষগুলির যে কোনও সেটে আবদ্ধ যমজ-প্রস্থের গ্রাফের সংখ্যা শুধুমাত্র একটি একক সূচকীয় ফ্যাক্টরের চেয়ে বড়, যে আবদ্ধ যমজ-প্রস্থের গ্রাফগুলির একটি সংলগ্ন লেবেলিং স্কিম রয়েছে যার প্রতি শীর্ষে শুধুমাত্র একটি লগারিদমিক সংখ্যা রয়েছে এবং তাদের বহুপদী আকারের সর্বজনীন গ্রাফ রয়েছে যেখানে আবদ্ধ যমজ-প্রস্থের প্রতিটি-ভার্টেক্স গ্রাফকে একটি প্ররোচিত উপগ্রাফ হিসাবে পাওয়া যেতে পারে। অ্যালগরিদম বহুপদী সময়ে সর্বাধিক একটিতে যমজ-প্রস্থের গ্রাফগুলি শনাক্ত করা যেতে পারে। যাইহোক, একটি প্রদত্ত গ্রাফের সর্বাধিক চারটিতে যমজ-প্রস্থ রয়েছে কিনা তা নির্ধারণ করা এনপি-সম্পূর্ণ, এবং 5/4 এর চেয়ে ভাল আনুমানিক অনুপাত সহ যমজ-প্রস্থের আনুমানিক অনুমান করা এনপি-শক্ত। সূচকীয় সময় অনুমানের অধীনে, যমজ-প্রস্থ গণনা করার জন্য-ভার্টেক্স গ্রাফগুলিতে কমপক্ষে সূচকীয় সময়ের প্রয়োজন হয়। বাস্তবে, স্যাট সমাধানকারী ব্যবহার করে মাঝারি আকারের গ্রাফের দ্বি-প্রস্থ গণনা করা সম্ভব। সীমাবদ্ধ যমজ-প্রস্থের গ্রাফের বেশিরভাগ পরিচিত পরিবারের জন্য, বহুপদী সময়ে সীমাবদ্ধ প্রস্থের একটি সংকোচন ক্রম তৈরি করা সম্ভব। একবার একটি সংকোচন ক্রম দেওয়া বা তৈরি করা হয়ে গেলে, এটি ব্যবহার করে অনেকগুলি বিভিন্ন অ্যালগরিদমিক সমস্যা সমাধান করা যেতে পারে, অনেক ক্ষেত্রে দ্বৈত-প্রস্থ সীমাবদ্ধ নয় এমন গ্রাফগুলির জন্য যতটা সম্ভব তার চেয়ে বেশি দক্ষতার সাথে। নীচে বিস্তারিত হিসাবে, এগুলির মধ্যে এনপি-হার্ড সমস্যার জন্য সঠিক প্যারামিটারাইজড অ্যালগরিদম এবং আনুমানিক অ্যালগরিদম অন্তর্ভুক্ত রয়েছে, পাশাপাশি এমন কিছু সমস্যা রয়েছে যার শাস্ত্রীয় বহুপদী সময় অ্যালগরিদম রয়েছে তবে তবুও আবদ্ধ যমজ-প্রস্থের অনুমান ব্যবহার করে গতি বাড়ানো যেতে পারে। প্যারামিটারাইজড অ্যালগরিদম গ্রাফের একটি অ্যালগরিদমিক সমস্যা যার সাথে একটি সম্পর্কিত প্যারামিটার থাকে তাকে ফিক্সড-প্যারামিটার ট্র্যাক্টেবল বলা হয় যদি এটির একটি অ্যালগরিদম থাকে যা শীর্ষ এবং প্যারামিটার মান সহ গ্রাফগুলিতে কিছু ধ্রুবক এবং গণনাযোগ্য ফাংশনের জন্য সময়মতো চলে। উদাহরণস্বরূপ, এর একটি চলমান সময় এই অর্থে স্থির-পরামিতি ট্র্যাক্টেবল হবে। বিশ্লেষণের এই শৈলীটি সাধারণত এমন সমস্যাগুলির ক্ষেত্রে প্রয়োগ করা হয় যার একটি পরিচিত পলিনোমিয়াল-টাইম অ্যালগরিদম নেই, কারণ অন্যথায় স্থির-পরামিতি ট্র্যাক্টেবিলিটি তুচ্ছ হবে। এই ধরনের অনেক সমস্যা একটি পরামিতি হিসাবে যমজ-প্রস্থ সহ স্থির-পরামিতি ট্র্যাক্টেবল হিসাবে দেখানো হয়েছে, যখন সীমাবদ্ধ প্রস্থের একটি সংকোচন ক্রম ইনপুটের অংশ হিসাবে দেওয়া হয়। এটি বিশেষত, উপরে তালিকাভুক্ত আবদ্ধ যমজ-প্রস্থের গ্রাফ পরিবারের ক্ষেত্রে প্রযোজ্য, যার জন্য একটি সংকোচন ক্রম দক্ষতার সাথে তৈরি করা যেতে পারে। যাইহোক, যখন গ্রাফের অন্য কোনও কাঠামো জানা যায় না, তখন নিম্ন দ্বৈত-প্রস্থের একটি নির্বিচারে গ্রাফের জন্য একটি ভাল সংকোচনের ক্রম কীভাবে খুঁজে পাওয়া যায় তা জানা যায় না। প্রদত্ত সংকোচন ক্রমের সাথে আবদ্ধ যমজ-প্রস্থের গ্রাফগুলির জন্য নির্দিষ্ট-পরামিতি ট্র্যাক্টেবল সমস্যাগুলির মধ্যে রয়েছেঃ প্রদত্ত গ্রাফটি গ্রাফের প্রথম-ক্রম যুক্তিতে কোনও প্রদত্ত বৈশিষ্ট্য মডেল করে কিনা তা পরীক্ষা করা। এখানে, সম্পত্তির যমজ-প্রস্থ এবং বর্ণনার দৈর্ঘ্য উভয়ই বিশ্লেষণের মাপকাঠি। এই ধরনের সমস্যাগুলির মধ্যে রয়েছে সীমাবদ্ধ আকারের সাবগ্রাফগুলির জন্য সাবগ্রাফ আইসোমরফিজম এবং সীমাবদ্ধ আকারের আচ্ছাদন বা প্রভাবশালী সেটগুলির জন্য ভার্টেক্স কভার এবং প্রভাবশালী সেট সমস্যা। বৈশিষ্ট্য বর্ণনাকারী যৌক্তিক সূত্রের দৈর্ঘ্যের উপর এই সাধারণ পদ্ধতির নির্ভরতা টেট্র্যাশনাল, তবে স্বাধীন সেট, প্রভাবশালী সেট এবং সম্পর্কিত সমস্যাগুলির জন্য এটি স্বাধীন বা প্রভাবশালী সেটের আকারে সূচকীয়তে হ্রাস করা যেতে পারে এবং সাবগ্রাফ আইসোমরফিজমের জন্য এটি সাবগ্রাফের শীর্ষগুলির সংখ্যায় ফ্যাক্টরিয়ালে হ্রাস করা যেতে পারে। উদাহরণস্বরূপ, একটি প্রদত্ত-অনুক্রম সহ একটি-ভার্টেক্স গ্রাফের জন্য একটি-ভার্টেক্স স্বাধীন সেট খুঁজে বের করার সময় হল একটি গতিশীল প্রোগ্রামিং অ্যালগরিদম যা সংকোচন অনুক্রমের সামনের দিকে লাল গ্রাফের ছোট সংযুক্ত সাবগ্রাফ বিবেচনা করে। সূচকীয় সময় অনুমানের অধীনে সূচকের লগারিদমিক ফ্যাক্টর পর্যন্ত এই সময়সীমাগুলি সর্বোত্তম। সম্পূর্ণরূপে ক্রমযুক্ত শীর্ষযুক্ত গ্রাফগুলিতে গ্রাফের প্রথম-ক্রম যুক্তির সম্প্রসারণের জন্য এবং এই ক্রমটি পরীক্ষা করতে পারে এমন যৌক্তিক পূর্বাভাসের জন্য, মডেল চেকিং এখনও আবদ্ধ যমজ-প্রস্থের বংশগত গ্রাফ পরিবারের জন্য স্থির-পরামিতি ট্র্যাক্টেবল, তবে সীমাহীন যমজ-প্রস্থের বংশগত পরিবারের জন্য (মানক জটিলতা-তাত্ত্বিক অনুমানের অধীনে) নয়। তাদের যমজ-প্রস্থ এবং তাদের বৃহত্তম চক্রের আকারের একটি ফাংশন দ্বারা আবদ্ধ বেশ কয়েকটি রঙ ব্যবহার করে আবদ্ধ যমজ-প্রস্থের রঙিন গ্রাফ। উদাহরণস্বরূপ, যমজ-প্রস্থের ত্রিভুজ-মুক্ত গ্রাফগুলি একটি লোভী রঙিন অ্যালগরিদম দ্বারা রঙ করা যেতে পারে যা তাদের সংকুচিত ক্রমের বিপরীত দিকে শীর্ষগুলিকে রঙ করে। এই ফলাফলটি দেখায় যে আবদ্ধ যমজ-প্রস্থের গ্রাফগুলি χ-সীমাবদ্ধ। সীমাবদ্ধ বিরল যমজ-প্রস্থের গ্রাফ পরিবারগুলির জন্য, সাধারণীকৃত রঙিন সংখ্যাগুলি সীমাবদ্ধ। এখানে, সাধারণীকৃত রঙিন সংখ্যাটি সর্বাধিক হয় যদি শীর্ষগুলি এমনভাবে রৈখিকভাবে ক্রমবদ্ধ করা যায় যে প্রতিটি শীর্ষ ক্রমের পূর্ববর্তী শীর্ষে পৌঁছতে পারে, ক্রমের পরবর্তী শীর্ষগুলির মধ্য দিয়ে দৈর্ঘ্যের পথের মাধ্যমে। ধ্রুপদী অ্যালগরিদমের গতি বৃদ্ধি আবদ্ধ দ্বৈত-প্রস্থের গ্রাফগুলিতে, একটি প্রস্থ-প্রথম অনুসন্ধান করা সম্ভব, শীর্ষযুক্ত গ্রাফের উপর, সময়ে, এমনকি যখন গ্রাফটি ঘন এবং এই সময়সীমার চেয়ে বেশি প্রান্ত থাকে। আনুমানিক অ্যালগরিদমগুলিতে যমজ-প্রস্থের আনুমানিক অ্যালগরিদমও প্রয়োগ করা হয়েছে। বিশেষত, আবদ্ধ যমজ-প্রস্থের গ্রাফগুলিতে, সীমাবদ্ধ আনুমানিক অনুপাত সহ ন্যূনতম প্রভাবশালী সেটের একটি আনুমানিক অনুমান খুঁজে পাওয়া সম্ভব। এটি আরও সাধারণ গ্রাফের বিপরীতে, যার জন্য লগারিদমিকের চেয়ে ভাল আনুমানিক অনুপাত পাওয়া এনপি-কঠিন। সর্বাধিক স্বাধীন সেট এবং গ্রাফ রঙের সমস্যাগুলি আবদ্ধ যমজ-প্রস্থের গ্রাফগুলিতে বহুপদী সময়ে, প্রতিটির জন্য, আনুমানিক অনুপাতের মধ্যে অনুমান করা যেতে পারে। বিপরীতে, আবদ্ধ যমজ-প্রস্থের অনুমান ব্যতীত, এই ফর্মের কোনও আনুমানিক অনুপাত অর্জন করা এনপি-কঠিন। রেফারেন্স আরও পড়া গ্রাফ অপরিবর্তনীয়