Subset Query

Given two set collections S={S1,,Sn}S = \{S_1, \dots, S_n\} and T={T1,,Tn}T = \{T_1, \dots, T_n\}, where all SiS_i and TiT_i are subsets of [d]:={1,,d}[d]:=\{1, \dots, d\}, is there a pair SiSS_i\in S, TjTT_j\in T such that SiTjS_i\subseteq T_j

Parameters

  • nn: number of sets in SS and number of sets in TT
  • dd: size of universe

Related Problems


Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table