Hardness of combinatorial optimization after adding one constraint - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:21:09Z http://mathoverflow.net/feeds/question/9647 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9647/hardness-of-combinatorial-optimization-after-adding-one-constraint Hardness of combinatorial optimization after adding one constraint Andrew 2009-12-24T00:12:17Z 2009-12-24T15:39:55Z <p>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})$$</p> <p>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$:</p> <p>$$\Phi_{x_i;j} = \max_{\mathbf{x} \in \left\{0,1\right\} ^N, x_i=j} f(\mathbf{x})$$</p> <p>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? <strike>Alternatively, is there an argument to be made that no such example exists?</strike></p> <p>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? </p> http://mathoverflow.net/questions/9647/hardness-of-combinatorial-optimization-after-adding-one-constraint/9648#9648 Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint Jonah Ostroff 2009-12-24T01:08:16Z 2009-12-24T01:08:16Z <p>Sure. We'll construct a normally trivial problem that turns into a question of four-coloring when we restrict one parameter.</p> <p>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 <i>is</i> proper, $f$ spits out the reciprocal of the number of colors used.</p> <p>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.</p> http://mathoverflow.net/questions/9647/hardness-of-combinatorial-optimization-after-adding-one-constraint/9681#9681 Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint Jonah Ostroff 2009-12-24T15:39:55Z 2009-12-24T15:39:55Z <p>Okay, here's a less contrived example. While minimal edge coverings can be found in polynomial time, finding a minimal <i>hyperedge</i> covering in general (equivalently, set covering) is NP-hard. On the other hand, finding such a covering when one of the hyperedges spans <i>all</i> vertices on the graph is easy: you just use that edge.</p> <p>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.</p>