A note on the depth function of combinatorial optimization problems

In a recent paper [Discrete Appl. Math. 43 (1993) 115–129], Kern formulates two conjectures on the relationship between the computational complexity of computing the depth function of a discrete optimization problem and the computational complexity of solving this optimization problem to optimality. In this note (that might be considered to be a kind of erratum to Kernʹs paper), we exhibit simple counterexamples to both conjectures under the assumption P≠NP.