I'm interested generally 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})$$


My question is this: suppose the original problem is solvable in polynomial time. Now, add a constraint that $x\_i = 0$ or $x\_i = 1$:


$$\Phi\_{x\_i;j} = \max\_{\mathbf{x} \in \left\{0,1\right\} ^N, x\_i=j} f(\mathbf{x})$$


Can you give me an example problem (preferably a moderately well-known combinatorial optimization problem) where $\Phi\_{x\_i;j}$ can no longer be found in polynomial time? Alternatively, is there an argument to be made that no such example exists?


Edit: clearly there are cases where a variable can switch between hard and easy problems, so examples will exist. I'm looking for a case that isn't "contrived" in this sense--preferably a well-known combinatorial problem that becomes harder when you condition on a partial solution. Is there some characteristic of functions/problems that describes whether they get harder or easier to solve as you condition on more variable assignments? 



Hardness of combinatorial optimization after adding one constraint
Okay, here's a less contrived example. While minimal edge coverings can be found in polynomial time, finding a minimal *hyperedge* covering in general (equivalently, set covering) is NP-hard. On the other hand, finding such a covering when one of the hyperedges spans *all* vertices on the graph is easy: you just use that edge.


So, given an arbitrary hypergraph, attach a new hyperedge to every vertex and look for a minimal cover. This can be done quickly. But constrain yourself to not using that edge, and you're back to the original NP-hard problem.


