Propagating Set Systems (PSS)

Input

A set system $(S, P_S)$, and subsets $S_o \subseteq S$ and $S_f \subseteq S$.

Problem

Does $S_o \stackrel{*}{\Rightarrow} S’$ such that $S’ \cap S_f \neq \varnothing$?

Definitions

A set system $(S, P_S)$ consists of a finite set $S$ and a finite set of productions $P_S$ of the form $X \to Y$, where $X$ and $Y$ are subsets of $S$. A set $B \subseteq S$ derives in one step a set $C \subseteq S$, written $B \Rightarrow C$, if and only if $$C = \bigcup_{X \to Y \in P_S, X \subseteq B} Y.$$

Relation $\stackrel{*}{\Rightarrow}$ denotes the reflexive, transitive closure of $\Rightarrow$. A propagating set system is a set system such that for every element $s \in S$, $\{s\} \to \{s\} \in P_S$.

Status

$\P$-complete (Monti and Roncato [1]).

Remarks

The reduction to show hardness is from a variant of GMSP. The general version of the problem is $\mathsf{PSPACE}$-complete.