## Hardness of combinatorial optimization after adding one constraint

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?

-

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.

-
For a graph $G$ on $n$ vertices, consider binary words of length $2n+1$. This will represent an assignment of colors 1-4 on the $n$ vertices, with the last bit telling us what the restriction on neighboring colors is. Namely, if the last digit is $i$, then $f$ spits out a 0 (calls it an improper coloring) if some pair of adjacent vertices have colors that are $i$ apart. When it is proper, $f$ spits out the reciprocal of the number of colors used.
 Thanks. Any $f$ with this sort of switching behavior of course will work--so clearly there are examples. I'm looking for a less contrived example. For example, if bipartite matching became hard when fixing $u_i$ to be matched to $v_j$, that would be ideal (I know that's not the case for bipartite matching--it's just an example). Also, are there conditions that can be placed on $f$ that cause this condition to hold or not hold? – Andrew Dec 24 2009 at 1:18