Take the 2-minute tour ×

This is a follow up to this question.


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


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|improve this question
add comment


Your Answer



Browse other questions tagged or ask your own question.