گراف کامل، وزندار و اقلیدسی (وزن یالهای هر مثلث در نامساوی مثلثی صدق میکنند!) G داده شده است. وزن راس v در گراف H برابر مجموع وزن یالهای مجاور راس v در H میباشد. هدف یافتن H (زیرگراف فراگیر و همبندی از G) است که بیشینهی وزن رئوسش کمینه باشد.
با فرض اینکه بزرگترین یال درخت فراگیر کمینهی G، α باشد، الگوریتمی چند جملهای ارائه دهید که زیر گرافی فراگیر و همبند از G بیابد که بیشینهی وزن رئوسش حداکثر 5α باشد.