Now return to the Fixed Charge Network Flow Problem (FCNP) of Chapter 11, definition 11.31 , and assume all data are integer.

(a) Develop and justify an expression for the length of a binary encoding for an instance in terms of the dimensions and parameters of the model.

(b) State the threshold version 1FCNP…2 for given threshold v.

(c) Explain why the threshold problem of (b)

belongs to NP.

(d) Detail a polynomial reduction from the 1FLP…2 of Exercise