I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. However, the input of problem A does not give me enough information to be able carry out all of these demands that problem B require.

My reduction will look something like this:

**A**(G(V, E), K) =
     a = V
     b = E
     P = **B**(a, b, K)
         return true

My question is if it is okay to ignore some of these demands and simply change the B problem to a simpler one which then would allow me to find a reduction which satisfies both problems?

I'm sorry for being so vague, it is a homework problem and I would like to not publish the details.


It doesn't matter what B exactly is, it could be graph problem or something else. Nobody cares as long as you construct its instance in polynomial time and it has a solution precisely when the instance of A has. Maybe you need to use some structure of A to construct B, but maybe some parts of A don't need to be used at all, who knows.

So precisely what you must do is follow the definitions, and then everything is fair game with no authority setting any special rules.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.