MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a follow up to this question.

I'm interested in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form $$\Phi = \max_{\mathbf{x} \in \left\{0,1\right\} ^N} f(\mathbf{x})$$

I'm looking for terminology or references that describe a property of these problems related to how much easier or more difficult they are to optimize as we constrain or expand the domain. This is motivated by looking at search procedures that successively assign values to a subset of variables, and I'd like to understand problem characteristics that make it so assigning more variables in the search tree will make the constrained combinatorial problem easier or harder.

It's not always the case that assigning variables makes the problem easier.

Example: suppose we have an optimization version of the subset-sum problem: find a subset of integers $S = \{x_1, \ldots, x_n\}$ whose sum is as large as possible but not larger than $t$. If one of the elements of $S$ is $t$, then the problem is trivial. As a less extreme example, if one of the elements of $S$, say $x_i$, is $t - k$ and another element, say $x_j$, is $k$, the problem is also trivial. However, if we branch in the search tree on $x_i$ not being used (or any other $x_{i'}$ being used where $i' \not = i, i' \not = j$), then we get a potentially hard optimization problem.

Conversely, Jonah raised the point in the previous question comments that if you think about this in the other direction--of trying to expand the domain to make a hard problem become easy, then

it's pretty unlikely that you can trivialize the problem of finding a perfect matching in a graph by adding just one edge. I haven't read all that much about this, but I'd even go so far as to guess that you need O(n) edges in general to make this easy (where n is the number of vertices).

Is there a term to describe this property--how much easier or more difficult can you make a class of problem by constraining $k$ variable values? Are there other cases where constraining variable values makes a problem harder (other than more examples of constraining a variable eliminating a trivial solution)?

I realize that "harder" and "trivial" need to be defined better. I'd also be curious about ideas on that.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.