Subgraf orientat tare-conex de cost minim

[•sandyxp]

Salut toata lumea,

Ma chinuie rau problema asta de cateva zile, si din cate am citit nu este deloc una usoara (este de tipul NP-Hard deci nu poate fi rezolvata numai prin algoritmi clasici, deterministi - probabil are o complexitate asemanatoare cu a Ciclului Hamiltonian de Cost Minim).
Mi se da un graf orientat tare conex (oricare ar fi nodurile u, v, exista drum de la u la v) si mi se cere un subgraf, tot tare conex, care sa fie de cost minim (suma costurilor muchiilor sale sa fie minim), sau, altfel spus, sa nu existe alt subgraf tare conex de cost mai mic decat al acestuia.
Prin subgraf inteleg aceleasi noduri, mai putine muchii.

Deja m-am convins ca algoritmi gen APM, sau flux, nu au cu ce sa ma ajute.

Orice idei ajuta