در واقع مسئله می‌خواهد که ما رئوس گراف را به چند مجموعه افراز کنیم که: ‎‎ ‎

1. ‎ ا ندازه‌ی هر مجموعه حداکثر ‎$s$‎ باشد.
2. برای هر مجموعه، رأسی در درخت (که ممکن است از خود آن مجموعه هم نباشد) وجود داشته باشد که فاصله‌اش با همه‌ی رئوس آن مجموعه حداکثر ‎$k$‎ باشد. این رأس درواقع جایی است که مهره‌ی متناظر با این مجموعه را در آن قرار می دهیم.

در ابتدا مسئله را در حالتی که فقط شرط دوم وجود دارد حل می کنیم. سپس الگوریتمی برای حل مسئله‌ی اصلی ارائه می‌دهیم‎.

‎ در حالتی که فقط شرط دوم وجود داشته باشد با یک بار ‎DFS‎ و به روش حریصانه مسئله را حل می‌کنیم. به این شکل که در هنگام اجرای DFS‎ ، فرض کنید به رأسی مثل ‎$v$‎ رسیدیم. پس از صدا زدن ‎DFS‎ همه‌ی بچه‌های ‎$v$‎، اگر دورترین نوه‌ای از ‎$v$‎ که هنوز توسط هیچ مهره‌ای پوشانده نشده است، فاصله‌ای به اندازه‌ی ‎$k$‎ با رأس ‎$v$‎ داشته باشد، در آن صورت روی رأس ‎$v$‎ یک مهره می‌گذاریم. برای اینکه بتوانیم دورترین نوه‌ی ‎$v$‎ را محاسبه کنیم، تابع ‎$v$‎ را به شکلی پیاده‌سازی می کنیم که به عنوان خروجی فاصله‌ی دورتین رأس پوشانده نشده را برگرداند. در این صورت با ماکسیمم گرفتن این مقدار بین همه‌ی بچه‌های ‎$v$‎ می‌توانیم فاصله‌ی دورترین نوه‌ی ‎$v$‎ که هنوز توسط هیج رأسی پوشانده نشده است را به‌دست آوریم. نکته ی دیگر این است که وقتی مهره‌ای در رأس ‎$v$‎ می‌گذاریم، این مهره می‌تواند نه تنها نوادگان خود، بلکه اجدادش و فرزندان آنها که با رأس ‎$v$‎ فاصله‌ی حداکثر ‎$k$‎ دارند را نیز بپوشاند. بنابراین در خروجی تابع علاوه بر فاصله‌ی دورترین فرزند پوشانده نشده، فاصله‌ی نزدیک ترین رأسی که روی آن مهره قرار دارد را نیز بر می‌گردانیم تا با استفاده از این مقدار، همه‌ی رأس های پوشیده شده توسط مهره‌ها را محاسبه کنیم. اثبات صحت این الگوریتم، به شکل کلی اثبات الگوریتم‌های حریصانه است و به خواننده واگذار می‌شود‎.

‎ با الگوریتم بالا ما توانستیم رئوس درخت را به کم‌ترین تعداد مجموعه افراز کنیم که فقط در شرط دوم صدق کنند. شرط اول از ما می‌خواهد که اندازه‌ی هر مجموعه از ‎$s$‎ بیش‌تر نشود. با در نظر گرفتن این شرط تغییری که باید در الگوریتم ایجاد کنیم این است که هر مهره دارای ظرفیت است و باید هر یک از رئوس را به یک مهره نسبت داد. یعنی ممکن است یک مهره تعداد زیادی از رئوس را بپوشاند، اما فقط تعدادی از آنها بتواند در مجموعه‌ی متناظر با آن مهره قرار گیرد، چون یک مهره ظرفیت محدودی دارد. بنابراین وقتی در الگوریتم حریصانه‌ی بالا به رأسی مثل ‎$v$‎ رسیدیم که فاصله‌ی دورترین رأس پوشیده نشده از آن ‎$k$‎ بود، علاوه بر این که تعیین می‌کنیم که در ‎$v$‎ باید یک مهره باشد، مشخص می‌کنیم که این مهره با چه رئوسی در ارتباط باشد. مجموعه ی رئوسی را که با ‎$v$‎ به فاصله ‎$k$‎ قرار دارند، ‎$A$‎ می‌نامیم. به طور حریصانه می‌توان اثبات کرد که مهره‌ی جدید می تواند با هر یک از اعضای ‎$A$‎ در ارتباط باشد. بنابراین اگر ‎$t=\lceil(|A|)/s\rceil$‎ در این صورت ما ‎$t$‎ مهره روی راس ‎$v$‎ قرار می دهیم. هر یک از این ‎$t$‎ مهره را به جز حداکثر یک مهره مثل ‎$m$‎ ، با ‎$s$‎ تا از رئوس مجموعه ‎$A$‎ مرتبط می سازیم و مهره‌ی ‎$m$‎ را با بقیه‌ی اعضای ‎$A$‎ مرتبط می‌کنیم. مهره‌ی ‎$m$‎ هنوز ظرفیت خالی دارد اما با توجه به اینکه ممکن است بقیه ی رئوس مرتبط با ‎$m$‎ خارج از زیر درخت ‎$v$‎ باشند، ظرفیت خالی ‎$m$‎ را در مراحل بعدی ‎DFS‎ پر می‌کنیم‎.

بنابراین الگوریتم ‎DFS‎ اولیه را اینگونه تغییر می‌دهیم که پس از اتمام ‎DFS‎ یک رأس مثل ‎$v$‎، به عنوان خروجی، لیستی از رئوسی که در زیر درخت ‎$v$‎ هستند و هنوز توسط مهره‌ای پوشیده نشده‌اند و همچنین لیستی از مهره‌هایی که در زیر درخت ‎$v$‎ هستند و ظرفیت خالی دارند را بر‌می‌گردانیم. حال وقتی که در حال اجرای ‎DFS‎ رأسی مثل ‎$u$‎ هستیم، در ابتدا DFS‎ همه بچه‌های ‎$u$‎ را فراخوانی می‌کنیم. لیست رئوس پوشیده نشده‌ی همه‌ی بچه‌های ‎$u$‎ را با هم ادغام می کنیم. همچنین لیست همه‌ی مهره‌های با ظرفیت خالی را نیز ادغام می‌کنیم. اگر در بین لیست بچه‌های پوشیده نشده، رئوسی با فاصله ی ‎$k$‎ از رأس ‎$u$‎ قرار داشند، آنها را از این لیست جدا می کنیم و در مجموعه‌ی ‎$A$‎ قرار می‌دهیم. این رئوس، رئوسی هستند که باید در این مرحله از ‎DFS‎، مهره‌ی متناظرشان مشخص شود. بنابراین اگر چنین رئوسی وچود نداشتند (یعنی ‎$|A| = 0$‎ )در این صورت DFS رأس ‎$u$‎ را خاتمه می‌دهیم و دو لیست مریوطه را به عنوان خروجی بر می‌گردانیم. اما اگر ‎$|A| > 0$‎، سعی می کنیم که رئوس مجموعه‌ی ‎$A$‎ را با استفاده از لیست مهره های موجود بپوشانیم. برای این کار به صورت حریصانه عمل می‌کنیم. یعنی ابتدا سراغ مهره‌ای می‌رویم که عمق بیش‌تری دارد و در آینده کم‌تر به درد می‌خورد. هر تعداد از رئوس مجموعه‌ی ‎$A$‎ را که می‌توانیم با این مهره می‌پوشانیم. در صورتی که ظرفیت این مهره پر شود آن را از لیست مهره‌های ظرفیت دار حذف می‌کنیم. سپس سراغ مهره‌ی بعدی (به ترتیب نزولی عمق مهره ها) می‌رویم و همین‌طور ادامه می‌دهیم. اگر در نهایت تعدادی از این رئوس باقی بماند، به میزان لازم مهره روی رأس ‎$u$‎ قرار می‌دهیم و در صورتی که مهره‌ای با ظرفیت خالی به وجود آمد آن را به لیست مهره‌ها اضافه می‌کنیم. در انتها لیست مهره‌ها و رئوس باقی‌مانده را به عنوان خروجی برمی‌گردانیم. علاوه بر این بعد از اینکه کل DFS‎ ها تمام شد، باید رئوس باقی‌مانده در لیست خروجی را به‌وسیله‌ی گذاشتن مهره در ریشه‌ی درخت ‎DFS‎ پوشاند‎.

با توجه به حریصانه بودن الگوریتم، با استفاده از روش معمولِ اثبات الگوریتم‌های حریصانه، (یعنی در نظر گرفتن اولین تفاوت جواب الگوریتم ما با جواب بهینه و شبیه کردن دو جواب به هم) می‌توان نشان داد که الگوریتم ما جواب بهینه را تولید می‌کند که با توجه به طولانی شدن راه حل اثبات این بخش نیز به خواننده واگذار می‌شود‎.

‎ پيچيدگي

بنابراین کل الگوریتم به صورت بازگشتی و در یک ‎DFS‎ خلاصه می‌شود. تابع ‎DFS‎ به ازای هر رأسی مثل ‎$v$‎ که صدا زده شد، به ترتیب کارهای زیر را انجام می‌دهیم: ‎‎ ‎

1. تابع ‎DFS را برای همه‌ی بچه‌های ‎$v$‎ صدا می‌زنیم.
2. ‎ در بین رأس‌های پوشیده نشده ی از نوادگان ‎$v$‎ ، آنهایی که فاصله شان تا ‎$v$‎ دقیقا ‎$k$‎ می‌باشد را در مجموعه‌ی ‎$A$‎ می ریزیم.
3. ‎ مهره‌هایی که در زیردرخت ‎$v$‎ قرار دارند و هنوز ظرفیت خالی دارند را به ترتیب نزولی عمق‌شان بررسی می‌کنیم و به ازای هر یک تا حد امکان، رئوس ‎$A$‎ را می پوشانیم.
4. در صورتی که هنوز مجموعه‌ی ‎$A$‎ رأسی پوشیده نشده دارد، به تعداد لازم ‎($t=\lceil(|A|)/s\rceil$)‎ مهره در رأس ‎$v$‎ قرار می‌دهیم.

‎ برای اینکه الگوریتم زمان اجرای مناسبی داشته باشد، باید هر یک از مراحل بالا را به شکل بهینه انجام داد. مثلا برای یافتن سریع مجموعه‌ی ‎$A$‎ می‌توانیم بعد از اتمام ‎DFS‎ هر رأس، آن را در یک آرایه از لیست‌ها که رئوس پوشیده نشده را برحسب عمق نگهداری می‌کند، قرار دهیم. در این صورت برای یافتن رئوسی که از ‎$v$‎ فاصله‌ی ‎$k$‎ دارند کافی است که لیست ‎$d[v]‎ + ‎k$‎ ام این آرایه را بررسی کنیم که ‎$d[v]$‎ برابر عمق ‎$v$‎ است (البته چون قبلا ممکن است این لیست پر شده باشد، باید قسمت انتهایی این لیست که مربوط به زیردرخت ‎$v$‎ است را بررسی کنیم).

اگر هر یک از قسمت های الگوریتم به شکل بهینه انجام شود، با توجه به اینکه در هر مرحله از ‎DFS‎ تعداد مهره‌ی های دارای ظرفیت خالی کم است، زمان اجرای الگوریتم بسیار کم و به طور شهودی چیزی در حدود ‎$O(n \log n)$‎ می‌شود.