The Capacitated Budgeted Minimum Cost Flow Problem with Unit Upgrading Costs

We consider a constraint minimum cost flow problem and show that it is in general NP-complete. For special graph classes we give (pseudo-)polynomial algorithms.