3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, this is definitely getting closer to what I'm trying to understand (and apologies for not knowing how to ask the question crisply the first time). For the more general part, should I open up a new thread? (i.e. Is there some way of describing functions that determines whether they get harder or easier to optimize as you condition on more variable assignments?) My suspicion is that most practical functions get easier to optimize as you assign more variables, but I'd like to better understand when this is not the case. Thanks again. $\endgroup$
    – Andrew
    Commented Dec 25, 2009 at 6:00
  • $\begingroup$ Well, in all the examples we've seen, it might even be misleading to say that the question gets harder when you constrain the domain. What's really happening is that the question got easier because we added a new option, and then we took that option away to make it hard again. So we should look at hard problems and ask whether just one new option can make it trivial. For instance, in the problem of choosing numbers from a list which sum to a given value, this is made trivial by introducing just that value to your list. $\endgroup$
    – Jonah Ostroff
    Commented Dec 25, 2009 at 21:09
  • $\begingroup$ By contrast, it's pretty unlikely that you can trivialize the problem of finding a perfect matching in a graph by adding just one edge. I haven't read all that much about this, but I'd even go so far as to guess that you need O(n) edges in general to make this easy. $\endgroup$
    – Jonah Ostroff
    Commented Dec 25, 2009 at 21:13
  • $\begingroup$ (Er, where n is the number of vertices.) $\endgroup$
    – Jonah Ostroff
    Commented Dec 25, 2009 at 21:14
  • $\begingroup$ Flipping it around like that is an interesting way of thinking about the question. I'm not exactly sure what it means to trivialize a perfect matching problem--something along the lines that a greedy algorithm will be optimal? Anyhow, this is definitely the sort of thing I would like to learn more about. Do you know of any relevant terminology or references that can be used to describe the difference between subset sum and matching in this regard? $\endgroup$
    – Andrew
    Commented Dec 29, 2009 at 9:04
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Andrew
    Commented Dec 24, 2009 at 1:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .