Embedding complexity and discrete optimization I: A new divide and conquer approach to discrete optimization

In this paper, we introduce a new and quite natural way of analyzing instances of discrete optimization problems in terms of what we call the embedding complexity of an associated more or (sometimes also) less canonical embedding of the (generally vast) solution space R of a given problem into a product $ \Pi_{e \in E} P_e $ of (generally many small) factor sets $ P_e (e \in E) $ so that the score $ s (\pi) $ of a solution $ \pi $, interpreted as an element $ \pi = (\pi_e)_{e\in E} \in \Pi_{e\in E} p_e $, can be computed additively by summing over the local scores $ s_e (\pi_e) $ of all of its components $ \pi_e $, for some appropriate score functions $ S_e (e \in E) $ defined on the various factor sets $ P_e $. This concept arises naturally within the context of a general Divide \& Conquer strategy for solving discrete optimization problems using dynamic-programming procedures. Relations with the treewidth concept and with linear-programming approaches to discrete optimization, as well as ways to exploit our approach to computing Boltzmann statistics for discrete optimization problems are indicated. In further papers, we will discuss these relations in more detail, we will relate embedding complexity also to other concepts of data representation like e.g., PQ-trees, and we will apply the ideas developed here towards designing schemes for solving specific optimization problems, e.g., the Steiner problem for graphs.