Weighted girth problem

Weighted girth problem --- задача о взвешенном обхвате.

Given a weighted undirected graph [math]\displaystyle{ G }[/math], the weighted girth problem (WGP) is to find a cycle having minimal weight. This problem is in general NP-hard but it can be solved in polynomial time, when [math]\displaystyle{ G }[/math] does not contain any cycle of a negative weight.

If we force the length of the cycle in the WGP to be less than some value [math]\displaystyle{ k }[/math], we obtain the cardinality constrained circuit problem (CCCP). If the cycle in WGP is forced to go through all vertices of [math]\displaystyle{ V(G) }[/math], we obtain the well-known traveling salesman problem.