Time complexity analysis of the minimal siphon extraction problem of Petri nets
Given a Petri net N = (P,T, E), a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case \Q\ greater than or equal to 1.
minimal siphons petri nets polynomial time solvability np-completeness strongly connectedness