Minimum t-spanner problem

Minimum [math]\displaystyle{ t }[/math]-spanner problem --- задача нахождения минимального [math]\displaystyle{ t }[/math]-стягивателя.

A [math]\displaystyle{ t }[/math]-spanner is called a minimum [math]\displaystyle{ t }[/math]-spanner of a weighted graph [math]\displaystyle{ G }[/math], if it has the minimum total edge weight among all [math]\displaystyle{ t }[/math]-spanners of [math]\displaystyle{ G }[/math]. The minimum [math]\displaystyle{ t }[/math]-spanner problem is formulated as follows.

Input: A graph [math]\displaystyle{ G }[/math] with associated (positive real valued) edge weights and a positive real value [math]\displaystyle{ W }[/math].

Question: Does [math]\displaystyle{ G }[/math] contain a [math]\displaystyle{ t }[/math]-spanner with a total edge weight at most [math]\displaystyle{ W }[/math]?