propongo un problema che non riesco a risolvere... lo posto in questa sezione perche' e' di teoria dei grafi/algoritmi discreti e la sezione informatica non mi sembra la piu'
adatta. Purtroppo richiede la conoscenza della programmazione dinamica ma anche se cade nel dimenticatoio puo' essere che prima o poi qualcuno trovi una risposta.
Sia $G$ un grafo completo non orientato, $k$ un naturale , sia data inoltre una funzione peso $w$ dai lati di $G$ ai naturali, $w:E(G)->NN$.
Trovare le equazioni di ricorrenza di prog dinamica per decidere se esiste una sotto cricca (subclique),$Q$, di $G$ tale che la somma dei pesi degli archi di $Q$
sia uguale a $k$.
In realta' sono quasi sicuro che sia $"NP-complete"$ ma mi chiedo se esistano delle ricorrenze che descrivano algo polinomiali almeno nel valore numerico di $k$...