Complexity of Extremal Set Decision Problem

Abstract

Let a set $[n]=\{1,2,\dots ,n\}$ be given. Finding a subset $S$ of $2^{[n]}$ with minimum cardinality such that, for any two distinct elements $x,y\in [n]$, there exist disjoint subsets $A_x,A_y\in \mathcal{S}$ such that $x\in A_x$ and $y\in A_y$ is called the \emph{extremal set} problem. In this paper, we define the Extremal Set Decision (ESD) Problem and study its complexity.