Hardness of combinatorial optimization after adding one constraint - MathOverflow

Hardness of combinatorial optimization after adding one constraint

2009-12-24T00:12:17Z

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?

Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint

2009-12-24T01:08:16Z

Sure. We'll construct a normally trivial problem that turns into a question of four-coloring when we restrict one parameter.

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.

Well, this is easy to maximize: just make every vertex the same color and choose the last digit to be 1. Congrats, you only used one color. But if our constraint is that the last digit is 0, then now you're asking whether the graph needs 1, 2, 3, 4, or more colors to properly color (in the usual sense), which you can't answer in polynomial time.

Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint

2009-12-24T15:39:55Z

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.