Return to Question

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. Also, is there some characteristic of functions/problems that makes them harder or easier when you condition on a variable assignment?

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?

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?

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. Also, is there some characteristic of functions/problems that makes them harder or easier when you condition on a variable assignment?