The complexity of minimum difference cover

The complexity of searching minimum difference covers, both in (Formula Not Shown) and in (Formula Not Shown), is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Formula Not Shown and in Formula Not Shown, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms.