Twin-width
દિશાહીન આલેખની જોડી-પહોળાઈ એ આલેખ સાથે સંકળાયેલ કુદરતી સંખ્યા છે, જેનો ઉપયોગ આલેખ અલ્ગોરિધમ્સની પરિમાણિત જટિલતાનો અભ્યાસ કરવા માટે થાય છે. સહજ ભાવે, તે ગ્રાફને આલેખ સાથે કેટલો સમાન છે તે માપે છે, ગ્રાફનો એક પ્રકાર કે જે વારંવાર જોડિયા, શિરોબિંદુઓ કે જે સમાન પડોશીઓ ધરાવે છે તેને એકસાથે ભેળવીને એક જ શિરોબિંદુમાં ઘટાડી શકાય છે. જોડિયા-પહોળાઈને પુનરાવર્તિત વિલિનીકરણના ક્રમમાંથી વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં શિરોબિંદુઓ જોડિયા હોવા જરૂરી નથી, પરંતુ પડોશીઓના લગભગ સમાન સમૂહ હોય છે. વ્યાખ્યા ટ્વીન-પહોળાઈ મર્યાદિત સરળ દિશાહીન આલેખ માટે વ્યાખ્યાયિત કરવામાં આવે છે. તેમાં શિરોબિંદુઓનો મર્યાદિત સમૂહ હોય છે, અને ધારોનો સમૂહ હોય છે જે શિરોબિંદુઓની અનિયમિત જોડી હોય છે. કોઈપણ શિરોબિંદુની ખુલ્લી પડોશ એ અન્ય શિરોબિંદુઓનો સમૂહ છે જેની સાથે તેને આલેખની ધારમાં જોડવામાં આવે છે; બંધ પડોશ ખુલ્લી પડોશમાંથી શિરોબિંદુને સામેલ કરીને રચાય છે. બે શિરોબિંદુઓ સાચા જોડિયા હોય છે જ્યારે તેઓ સમાન બંધ પડોશી હોય છે, અને ખોટા જોડિયા હોય છે જ્યારે તેઓ સમાન ખુલ્લા પડોશી હોય છે; વધુ સામાન્ય રીતે, સાચા જોડિયા અને ખોટા જોડિયા બંનેને લાયકાત વિના જોડિયા કહી શકાય. આલેખોમાં ઘણી સમકક્ષ વ્યાખ્યાઓ હોય છે, પરંતુ તેમાંથી એક એ છે કે આ એવા આલેખો છે જે કોઈપણ બે જોડિયા શિરોબિંદુઓને વારંવાર શોધવા અને તેમને એક જ શિરોબિંદુમાં મર્જ કરવાની પ્રક્રિયા દ્વારા એક જ શિરોબિંદુમાં ઘટાડી શકાય છે. આલેખ માટે, આ ઘટાડાની પ્રક્રિયા હંમેશા સફળ રહેશે, ભલે દરેક તબક્કે જોડિયાની મર્જ કરવાની પસંદગી કરવામાં આવે. ગ્રાફ માટે કે જે ગ્રાફ નથી, તે હંમેશા બેથી વધુ શિરોબિંદુઓ સાથે સબગ્રાફમાં અટવાઇ જશે જેમાં કોઈ જોડિયા નથી. ટ્વીન-વિડ્થની વ્યાખ્યા આ ઘટાડાની પ્રક્રિયાની નકલ કરે છે. સંકોચન ક્રમ, આ સંદર્ભમાં, પગલાંઓનો ક્રમ છે, જે આપેલ આલેખથી શરૂ થાય છે, જેમાં દરેક પગલું શિરોબિંદુઓની જોડીને એક શિરોબિંદુ દ્વારા બદલે છે. આ આલેખનો ક્રમ ઉત્પન્ન કરે છે, જેમાં ધાર લાલ અને કાળા રંગની હોય છે; આપેલ આલેખમાં, બધી ધાર કાળી હોવાનું માનવામાં આવે છે. જ્યારે બે શિરોબિંદુઓને એક જ શિરોબિંદુ દ્વારા બદલવામાં આવે છે, ત્યારે નવા શિરોબિંદુની પડોશ એ બદલાયેલા શિરોબિંદુઓના પડોશોનું જોડાણ છે. આ નવા પડોશમાં, બંને શિરોબિંદુઓના પડોશમાં કાળી ધારમાંથી આવતી ધાર કાળી રહે છે; અન્ય તમામ ધાર લાલ રંગની હોય છે. સંકોચન ક્રમને એ-ક્રમ કહેવામાં આવે છે, જો સમગ્ર ક્રમમાં, દરેક શિરોબિંદુ સૌથી વધુ લાલ ધારને સ્પર્શે છે. આલેખની બેવડું-પહોળાઈ એ સૌથી નાનું મૂલ્ય છે જેના માટે તે-ક્રમ ધરાવે છે. ગાઢ આલેખમાં હજુ પણ જોડી-પહોળાઈ બંધાયેલ હોઈ શકે છે; દાખલા તરીકે, આલેખમાં તમામ સંપૂર્ણ આલેખનો સમાવેશ થાય છે. જોડી-પહોળાઈ, વિરલ જોડી-પહોળાઈની વિવિધતા, વ્યક્તિગત આલેખને બદલે આલેખના પરિવારોને લાગુ પડે છે. ગ્રાફના પરિવાર માટે કે જે પ્રેરિત સબગ્રાફ લેવા હેઠળ બંધ હોય છે અને બેવડું પહોળાઈ ધરાવે છે, નીચેના ગુણધર્મો સમકક્ષ છેઃ પરિવારમાં ગ્રાફ વિરલ હોય છે, એટલે કે તેમની પાસે સંખ્યાબંધ ધાર હોય છે જે તેમની શિરોબિંદુઓની સંખ્યાના રેખીય કાર્ય દ્વારા બંધાયેલ હોય છે. કુટુંબમાં તમામ સંપૂર્ણ દ્વિપક્ષી આલેખનો સમાવેશ થતો નથી. આપેલ કુટુંબમાં આલેખના તમામ પેટા આલેખનો પરિવાર બેવડું-પહોળાઈ ધરાવે છે. આ પરિવારે મર્યાદિત વિસ્તરણ કર્યું છે, જેનો અર્થ છે કે તેના તમામ છીછરા નાના બાળકો વિરલ છે. આવા કુટુંબમાં વિરલ ટ્વીન-પહોળાઈ હોવાનું કહેવાય છે. ટ્વીન-વિડ્થની વિભાવનાને આલેખથી લઈને વિવિધ સંપૂર્ણપણે ક્રમબદ્ધ માળખાઓ (તેમના શિરોબિંદુઓ પર કુલ ક્રમથી સજ્જ આલેખ સહિત) સુધી સામાન્યીકૃત કરી શકાય છે, અને બિન-ક્રમબદ્ધ આલેખ કરતાં ક્રમબદ્ધ માળખાઓ માટે ઘણી રીતે સરળ છે. બંધાયેલ ડિગ્રી કરતાં વિવિધ જરૂરિયાતો સાથે સંકોચન ક્રમનો ઉપયોગ કરીને આલેખની પહોળાઈની અન્ય કલ્પનાઓ માટે સમકક્ષ વ્યાખ્યાઓ ઘડવી પણ શક્ય છે. બાઉન્ડેડ ટ્વીન-વિડ્થ આલેખના આલેખમાં ટ્વીન-વિડ્થ શૂન્ય હોય છે. આલેખ માટે ઘટાડાની પ્રક્રિયામાં, કોઈ લાલ ધાર હશે નહીંઃ જ્યારે બે શિરોબિંદુઓ ભળી જાય છે, ત્યારે તેમના પડોશ સમાન હોય છે, તેથી બે પડોશમાંથી માત્ર એકમાંથી લાલ રંગની ધાર આવતી નથી. અન્ય કોઈપણ આલેખમાં, કોઈપણ સંકોચન ક્રમ કેટલીક લાલ ધાર પેદા કરશે, અને ટ્વીન-પહોળાઈ શૂન્ય કરતા વધારે હશે. મહત્તમ ત્રણ શિરોબિંદુઓ ધરાવતા પાથ ગ્રાફ આલેખ છે, પરંતુ દરેક મોટા પાથ ગ્રાફમાં બે-પહોળાઈ હોય છે. માર્ગની છેલ્લી બે ધારને વારંવાર મર્જ કરતા સંકોચન ક્રમ માટે, એક મર્જ કરેલા શિરોબિંદુની માત્ર ધારની ઘટના લાલ હશે, તેથી આ 1-ક્રમ છે. વૃક્ષોની પહોળાઈ વધુમાં વધુ બે હોય છે, અને કેટલાક વૃક્ષો માટે આ ચુસ્ત હોય છે. કોઈપણ વૃક્ષ માટે 2-સંકોચન ક્રમ મૂળ પસંદ કરીને શોધી શકાય છે, અને પછી વારંવાર એક જ મૂળ ધરાવતા બે પાંદડાઓને ભેળવી શકાય છે અથવા, જો આ શક્ય ન હોય તો, સૌથી ઊંડા પાંદડાને તેના મૂળમાં ભેળવી શકાય છે. માત્ર લાલ ધાર પાંદડાઓને તેમના માતાપિતા સાથે જોડે છે, અને જ્યારે એક જ પિતૃ પર બે હોય ત્યારે તેમને મર્જ કરી શકાય છે, લાલ ડિગ્રીને વધુમાં વધુ બે રાખી શકાય છે. વધુ સામાન્ય રીતે, આલેખના નીચેના વર્ગોમાં બંધાયેલ જોડી-પહોળાઈ હોય છે, અને તેમના માટે બંધાયેલ પહોળાઈનો સંકોચન ક્રમ બહુપદી સમયમાં મળી શકે છેઃ બંધાયેલ સમૂહ-પહોળાઈ અથવા બંધાયેલ ક્રમ-પહોળાઈનો દરેક આલેખ પણ બંધાયેલ જોડી-પહોળાઈ ધરાવે છે. જોડી-પહોળાઈ સમૂહ-પહોળાઈમાં સૌથી વધુ ઘાતાંકીય હોય છે, અને ક્રમ-પહોળાઈમાં સૌથી વધુ બમણી ઘાતાંકીય હોય છે. આ આલેખમાં, દાખલા તરીકે, અંતર-વંશપરંપરાગત આલેખ, બંધાયેલ મૂલ્યો માટે-પર્ણ શક્તિઓ અને બંધાયેલ ત્રિ-પહોળાઈના આલેખનો સમાવેશ થાય છે. ઉદાસીનતા આલેખ (સમાનરૂપે, એકમ અંતરાલ આલેખ અથવા યોગ્ય અંતરાલ આલેખ) મહત્તમ બે પર બેવડું પહોળાઈ ધરાવે છે. એકમ ડિસ્ક આલેખ, જે એકમ ડિસ્કના સમૂહમાંથી વ્યાખ્યાયિત કરવામાં આવે છે, જે સમતલના દરેક બિંદુને મર્યાદિત સંખ્યામાં આવરી લે છે, તેમાં જોડી-પહોળાઈ હોય છે. ઉચ્ચ પરિમાણોમાં યુનિટ બોલ ગ્રાફ માટે પણ આ જ સાચું છે. પ્રતિબંધિત ક્રમચય પેટર્ન સાથેના ક્રમચયમાંથી આવતા ક્રમચય આલેખમાં જોડી-પહોળાઈ હોય છે. આ પ્રતિબંધિત પેટર્ન સાથેના ક્રમચયો પર અલ્ગોરિધમિક સમસ્યાઓ પર ટ્વીન-પહોળાઈ લાગુ કરવાની મંજૂરી આપે છે. પ્રતિબંધિત સગીર દ્વારા વ્યાખ્યાયિત આલેખના દરેક કુટુંબમાં બેવડું-પહોળાઈ હોય છે. દાખલા તરીકે, વેગનરના પ્રમેય અનુસાર, સમતલીય આલેખ માટે પ્રતિબંધિત ગૌણ બે આલેખ છે અને તેથી સમતલીય આલેખમાં જોડી-પહોળાઈ હોય છે. બાઉન્ડેડ સ્ટૅક નંબર અથવા બાઉન્ડેડ કતાર નંબરનો દરેક આલેખ પણ બાઉન્ડેડ ટ્વીન-વિડ્થ ધરાવે છે. ત્યાં બાઉન્ડેડ સ્પાર્સ ટ્વીન-વિડથના આલેખના પરિવારો અસ્તિત્વમાં છે જેમાં બાઉન્ડેડ સ્ટેક નંબર નથી, પરંતુ કતાર નંબર માટે અનુરૂપ પ્રશ્ન ખુલ્લો રહે છે. બાઉન્ડેડ ટ્વીન-પહોળાઈના કોઈપણ બે આલેખનો મજબૂત ગુણાકાર, જેમાંથી એક બાઉન્ડેડ ડિગ્રી ધરાવે છે, તે ફરીથી બાઉન્ડેડ ટ્વીન-પહોળાઈ ધરાવે છે. આનો ઉપયોગ એવા આલેખના વર્ગોના બંધાયેલા બેવડાં-પહોળાઈને સાબિત કરવા માટે થઈ શકે છે કે જે રસ્તાઓના મજબૂત ઉત્પાદનો અને બંધાયેલા-ત્રિ-પહોળાઈવાળા આલેખમાં વિઘટન ધરાવે છે, જેમ કે-સમતલીય આલેખ. આલેખના લેક્સિકોગ્રાફિક ઉત્પાદન માટે, ટ્વીન-પહોળાઈ બરાબર બે પરિબળ આલેખની પહોળાઈની મહત્તમ છે. ટ્વીન-વિડ્થ પણ કેટલાક અન્ય પ્રમાણભૂત ગ્રાફ ઉત્પાદનો હેઠળ સારી રીતે વર્તે છે, પરંતુ ગ્રાફના મોડ્યુલર ઉત્પાદન હેઠળ નહીં. બંધાયેલા જોડિયા-પહોળાઈના આલેખના દરેક વંશપરંપરાગત પરિવારમાં, તેના આલેખના શિરોબિંદુઓ માટે કુલ ક્રમનો પરિવાર શોધવો શક્ય છે જેથી પ્રેરિત સબગ્રાફ પર વારસાગત ક્રમ પણ પરિવારમાં એક ક્રમ હોય, અને જેથી આ ક્રમના સંદર્ભમાં પરિવાર નાનો હોય. આનો અર્થ એ છે કે, શિરોબિંદુઓ પરના કુલ ક્રમ માટે, તે ક્રમ સાથે સુસંગત કુટુંબમાં આલેખની સંખ્યા સૌથી વધુ એકલ રીતે ઘાતાંકીય હોય છે. તેનાથી વિપરીત, આ અર્થમાં નાના ક્રમાંકિત આલેખનો દરેક વારસાગત પરિવાર બેવડું-પહોળાઈ ધરાવે છે. મૂળરૂપે એવું અનુમાન કરવામાં આવ્યું હતું કે લેબલવાળા આલેખનો દરેક વારસાગત પરિવાર જે નાનો છે, તે અર્થમાં કે આલેખોની સંખ્યા વધુમાં વધુ એક જ ઘાતાંકીય પરિબળ વખત છે, તે બેવડું-પહોળાઈ ધરાવે છે. જો કે, આ અનુમાનને અનંત કેલે ગ્રાફના પ્રેરિત સબગ્રાફ્સના પરિવારનો ઉપયોગ કરીને નકારી કાઢવામાં આવ્યું હતું, જે લેબલવાળા ગ્રાફ તરીકે નાના હોય છે પરંતુ તેમાં બંધાયેલ ટ્વીન-પહોળાઈ હોતી નથી. આલેખના નીચેના પરિવારોમાં અનબાઉન્ડ ટ્વીન-પહોળાઈના આલેખ અસ્તિત્વમાં છેઃ બાઉન્ડેડ ડિગ્રીના આલેખ. અંતરાલ આલેખ. એકમ ડિસ્ક આલેખ. આ દરેક કિસ્સામાં, પરિણામ ગણતરીની દલીલ દ્વારા અનુસરવામાં આવે છેઃ આપેલ પ્રકારનાં વધુ આલેખ હોય છે, જેમાં બંધાયેલા બેવડાં-પહોળાઈના આલેખ હોઈ શકે છે. ગુણધર્મો જો આલેખમાં જોડી-પહોળાઈ બંધાયેલ હોય, તો સંકોચનનું બહુમુખી વૃક્ષ શોધવું શક્ય છે. આ સંકોચન ક્રમનો એક મોટો પરિવાર છે, જે તમામ કેટલીક (મોટી) બંધાયેલ પહોળાઈ ધરાવે છે, જેથી દરેક ક્રમમાં દરેક પગલા પર શિરોબિંદુઓની રેખીય રીતે ઘણી અસંબદ્ધ જોડીઓ હોય છે, જેમાંથી દરેકને ક્રમમાં આગળના પગલા પર સંકુચિત કરી શકાય છે. આ પરથી એવું જાણવા મળે છે કે આપેલ શિરોબિંદુઓના કોઈપણ સમૂહ પર બંધાયેલા જોડિયા-પહોળાઈના આલેખની સંખ્યા માત્ર એક જ ઘાતાંકીય પરિબળ કરતાં મોટી હોય છે, કે બંધાયેલા જોડિયા-પહોળાઈના આલેખમાં માત્ર શિરોબિંદુ દીઠ બિટ્સની લઘુગણક સંખ્યા સાથે સંલગ્નતા લેબલિંગ યોજના હોય છે, અને તેમની પાસે બહુપદી કદના સાર્વત્રિક આલેખ હોય છે જેમાં બંધાયેલા જોડિયા-પહોળાઈના દરેક-વર્ટેક્સ આલેખને પ્રેરિત સબગ્રાફ તરીકે શોધી શકાય છે. અલ્ગોરિધમ્સ બહુપદી સમયમાં મહત્તમ એક પર ટ્વીન-પહોળાઈના આલેખને ઓળખી શકાય છે. જો કે, તે નક્કી કરવા માટે એન. પી.-પૂર્ણ છે કે શું આપેલ આલેખમાં મહત્તમ ચાર પર ટ્વીન-પહોળાઈ છે, અને 5/4 કરતા વધુ સારા અંદાજ ગુણોત્તર સાથે ટ્વીન-પહોળાઈનો અંદાજ કાઢવા માટે એન. પી.-હાર્ડ છે. ઘાતાંકીય સમયની પૂર્વધારણા હેઠળ, ટ્વીન-વિડ્થની ગણતરી કરવા માટે-વર્ટેક્સ આલેખમાં ઓછામાં ઓછો ઘાતાંકીય સમયની જરૂર પડે છે. વ્યવહારમાં, SAT સોલ્વર્સનો ઉપયોગ કરીને મધ્યમ કદના આલેખની બે-પહોળાઈની ગણતરી કરવી શક્ય છે. બંધાયેલા જોડિયા-પહોળાઈના આલેખના મોટાભાગના જાણીતા પરિવારો માટે, બહુપદી સમયમાં બંધાયેલ પહોળાઈનો સંકોચન ક્રમ બનાવવો શક્ય છે. એકવાર સંકોચન ક્રમ આપવામાં આવ્યો હોય અથવા બનાવવામાં આવ્યો હોય, તો તેનો ઉપયોગ કરીને ઘણી જુદી જુદી અલ્ગોરિધમિક સમસ્યાઓ ઉકેલી શકાય છે, ઘણા કિસ્સાઓમાં બંધાયેલા ટ્વીન-પહોળાઈ ન ધરાવતા આલેખ માટે શક્ય હોય તેના કરતા વધુ અસરકારક રીતે. નીચે વિગતવાર જણાવ્યા મુજબ, તેમાં એન. પી.-હાર્ડ સમસ્યાઓ માટે ચોક્કસ પરિમાણિત અલ્ગોરિધમ્સ અને અંદાજિત અલ્ગોરિધમ્સનો સમાવેશ થાય છે, તેમજ કેટલીક સમસ્યાઓ કે જે શાસ્ત્રીય બહુપદી સમય અલ્ગોરિધમ્સ ધરાવે છે પરંતુ તેમ છતાં બંધાયેલ ટ્વીન-પહોળાઈની ધારણાનો ઉપયોગ કરીને તેને ઝડપી બનાવી શકાય છે. પેરામિટરાઇઝ્ડ એલ્ગોરિધમ્સ સંબંધિત પરિમાણ ધરાવતા આલેખ પરની એક અલ્ગોરિધમિક સમસ્યાને ફિક્સ્ડ-પેરામીટર ટ્રેક્ટેબલ કહેવામાં આવે છે જો તેમાં એક અલ્ગોરિધમ હોય, જે શિરોબિંદુઓ અને પરિમાણ મૂલ્યવાળા આલેખ પર, કેટલાક સ્થિર અને ગણતરીપાત્ર કાર્ય માટે સમયસર ચાલે છે. દાખલા તરીકે, નો ચાલી રહેલો સમય આ અર્થમાં નિશ્ચિત-પરિમાણ ટ્રેક્ટેબલ હશે. વિશ્લેષણની આ શૈલી સામાન્ય રીતે એવી સમસ્યાઓ પર લાગુ થાય છે કે જેમાં જાણીતા બહુપદી-સમય અલ્ગોરિધમ નથી, કારણ કે અન્યથા નિશ્ચિત-પરિમાણ ટ્રેક્ટેબિલિટી તુચ્છ હશે. આવી ઘણી સમસ્યાઓ નિશ્ચિત-પરિમાણ દ્વારા પાર કરી શકાય તેવી હોવાનું દર્શાવવામાં આવ્યું છે, જેમાં દ્વિ-પહોળાઈ પરિમાણ તરીકે હોય છે, જ્યારે બાઉન્ડેડ પહોળાઈનો સંકોચન ક્રમ ઇનપુટના ભાગ રૂપે આપવામાં આવે છે. આ ખાસ કરીને, ઉપર સૂચિબદ્ધ બાઉન્ડેડ ટ્વીન-વિડથના ગ્રાફ પરિવારોને લાગુ પડે છે, જેના માટે સંકોચન ક્રમ અસરકારક રીતે બનાવી શકાય છે. જો કે, ગ્રાફમાં અન્ય કોઈ માળખું જાણીતું ન હોય ત્યારે, ઓછી ટ્વીન-પહોળાઈના મનસ્વી ગ્રાફ માટે સારો સંકોચન ક્રમ કેવી રીતે શોધવો તે જાણીતું નથી. આપેલ સંકોચન ક્રમ સાથે બાઉન્ડેડ ટ્વીન-પહોળાઈના આલેખ માટે નિશ્ચિત-પરિમાણ ટ્રેક્ટેબલ સમસ્યાઓમાં નીચેનાનો સમાવેશ થાય છેઃ આપેલ આલેખ આલેખના પ્રથમ ક્રમના તર્કમાં આપેલ કોઈ ગુણધર્મને મોડેલ કરે છે કે કેમ તે ચકાસવું. અહીં, મિલકતની ટ્વીન-પહોળાઈ અને વર્ણનની લંબાઈ બંને વિશ્લેષણના પરિમાણો છે. આ પ્રકારની સમસ્યાઓમાં બાઉન્ડેડ કદના સબગ્રાફ માટે સબગ્રાફ આઇસોમોર્ફિઝમ અને બાઉન્ડેડ કદના કવર્સ અથવા ડોમિનેટિંગ સેટ માટે શિરોબિંદુ આવરણ અને ડોમિનેટિંગ સેટ સમસ્યાઓનો સમાવેશ થાય છે. ગુણધર્મનું વર્ણન કરતા તાર્કિક સૂત્રની લંબાઈ પર આ સામાન્ય પદ્ધતિઓની નિર્ભરતા ટેટ્રેશનલ છે, પરંતુ સ્વતંત્ર સમૂહ, પ્રભુત્વ ધરાવતા સમૂહ અને સંબંધિત સમસ્યાઓ માટે તેને સ્વતંત્ર અથવા પ્રભુત્વ ધરાવતા સમૂહના કદમાં ઘાતાંકીયમાં ઘટાડી શકાય છે, અને સબગ્રાફ આઇસોમોર્ફિઝમ માટે તેને સબગ્રાફના શિરોબિંદુઓની સંખ્યામાં ફેક્ટોરિયલમાં ઘટાડી શકાય છે. દાખલા તરીકે, આપેલ-ક્રમ સાથે-વર્ટેક્સ આલેખ માટે-વર્ટેક્સ સ્વતંત્ર સમૂહ શોધવાનો સમય, ગતિશીલ પ્રોગ્રામિંગ અલ્ગોરિધમ દ્વારા છે, જે સંકોચન ક્રમની આગળની દિશામાં લાલ આલેખના નાના જોડાયેલા પેટા આલેખને ધ્યાનમાં લે છે. ઘાતાંકીય સમયની પૂર્વધારણા હેઠળ, ઘાતાંકમાં લઘુગણક પરિબળો સુધી, આ સમય સીમાઓ શ્રેષ્ઠ છે. આલેખના પ્રથમ ક્રમના તર્કને સંપૂર્ણપણે ક્રમાંકિત શિરોબિંદુઓ સાથેના આલેખમાં વિસ્તારવા માટે, અને તાર્કિક આગાહીઓ કે જે આ ક્રમને ચકાસી શકે છે, મોડેલ ચકાસણી હજુ પણ નિશ્ચિત-પરિમાણ છે જે બંધાયેલા જોડિયા-પહોળાઈના વારસાગત આલેખ પરિવારો માટે યોગ્ય છે, પરંતુ (પ્રમાણભૂત જટિલતા-સૈદ્ધાંતિક ધારણાઓ હેઠળ) અમર્યાદિત જોડિયા-પહોળાઈના વારસાગત પરિવારો માટે નહીં. તેમના જોડિયા-પહોળાઈ અને તેમના સૌથી મોટા જૂથના કદના કાર્ય દ્વારા બંધાયેલા સંખ્યાબંધ રંગોનો ઉપયોગ કરીને બંધાયેલા જોડિયા-પહોળાઈના રંગ આલેખ. દાખલા તરીકે, જોડિયા-પહોળાઈના ત્રિકોણ-મુક્ત આલેખને લોભી રંગ અલ્ગોરિધમ દ્વારા રંગીન કરી શકાય છે, જે શિરોબિંદુઓને તેઓ જે ક્રમમાં સંકોચાઈ ગયા હતા તેની વિરુદ્ધમાં રંગ આપે છે. આ પરિણામ દર્શાવે છે કે બંધાયેલા જોડિયા-પહોળાઈના આલેખ χ-બંધાયેલા છે. બંધાયેલ વિરલ ટ્વીન-પહોળાઈના આલેખ પરિવારો માટે, સામાન્યીકૃત રંગ સંખ્યાઓ બંધાયેલ છે. અહીં, સામાન્યીકૃત રંગ નંબર વધુમાં વધુ હોય છે જો શિરોબિંદુઓને એવી રીતે રેખીય રીતે ક્રમબદ્ધ કરી શકાય કે દરેક શિરોબિંદુ ક્રમમાં સૌથી અગાઉના શિરોબિંદુઓ સુધી પહોંચી શકે, ક્રમમાં પછીના શિરોબિંદુઓમાંથી લંબાઈના માર્ગો દ્વારા. શાસ્ત્રીય અલ્ગોરિધમ્સના સ્પીડઅપ્સ બાઉન્ડેડ ટ્વીન-વિડ્થના ગ્રાફમાં, જ્યારે ગ્રાફ ગાઢ હોય અને આ સમય મર્યાદા કરતાં વધુ ધાર હોય ત્યારે પણ, શિરોબિંદુઓ સાથે ગ્રાફ પર, પહોળાઈ-પ્રથમ શોધ કરવી શક્ય છે. અંદાજ અલ્ગોરિધમ્સમાં અંદાજ અલ્ગોરિધમ્સ ટ્વીન-વિડ્થ પણ લાગુ કરવામાં આવ્યા છે. ખાસ કરીને, બંધાયેલા જોડિયા-પહોળાઈના આલેખમાં, બંધાયેલા અંદાજ ગુણોત્તર સાથે લઘુત્તમ પ્રભુત્વ ધરાવતા સમૂહનો અંદાજ શોધવો શક્ય છે. આ વધુ સામાન્ય આલેખથી વિપરીત છે, જેના માટે લઘુગણક કરતાં વધુ સારો અંદાજ ગુણોત્તર મેળવવો એન. પી.-મુશ્કેલ છે. મહત્તમ સ્વતંત્ર સમૂહ અને આલેખ રંગની સમસ્યાઓને બાઉન્ડેડ ટ્વીન-પહોળાઈના આલેખ પર બહુપદી સમયમાં, દરેક માટે, અંદાજિત ગુણોત્તરમાં અંદાજિત કરી શકાય છે. તેનાથી વિપરીત, બાઉન્ડેડ ટ્વીન-વિડ્થની ધારણા વિના, આ સ્વરૂપનો કોઈપણ અંદાજ ગુણોત્તર પ્રાપ્ત કરવો એન. પી.-મુશ્કેલ છે. સંદર્ભો વધુ વાંચન આલેખ અપરિવર્તનશીલ