I know that integer multicommodity flow is NP-complete. It was proven in

On the complexity of time table and multi-commodity flow problems

that any SAT problem can be reduced to an integer multicommodity problem.

I also know that the ASP version of SAT (finding additional solutions to a SAT problem when a number of solutions are already known) is also NP-complete. It was shown in

Complexity and completeness of finding another solution.

My question: is the ASP version of integer multicommodity NP-complete as well?

The authors of the second article defined an ASP reduction, and proved that if one problem can be reduced by ASP-reduction to a problem that is ASP-complete, then that problem is also ASP-complete.

I never formally studied computer science, and I'm not sure if the reduction between integer multicommodity to SAT is an ASP reduction... I'd be grateful if someone from this field would know the answer.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.