I have found that finding a minimal siphon containing a set of places in general Petri Net is NP-complete. However, I am curious if this problem lands into a smaller complexity class if we only are trying to find a siphon, where the set of places is a trap T and we further require that the largest trap inside the siphon we find has to be T.

Or does this problem get easier if we instead require that this search is done in a Free Choice Petri Net, where many decision problems are much easier to solve than in a general Petri Net.

I have looked around, but it doesn't seem to be a question many people are asking, so I haven't found anything so far. Are those two "simpler" problems also NP-complete or are they in some smaller complexity class?

| cite | improve this question | | | | |

Your Answer

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

Browse other questions tagged or ask your own question.