# Restricted k-set cover is in NL or L

Restricted $k$-set cover:

Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.

Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\}, i_1=min(S_1),i_2=min(S_1\cap S_{i_1}), \cdots, i_k=min(S_1\cap S_{i_2}\cap\cdots\cap S_{i_{k-1}})$

This problem is Restricted $k$-set cover I want to know the above problem is in L or NL?

I trying to show this problem is in NL-complete. But I did not get any problem which is NL-complete connects to this problem.

• [Check this out.][1] [1]: books.google.com/… Jun 2, 2017 at 2:44
• @TayfunPay their (given ref) definition of restricted $k$-set cover different from this definition. Even in their original paper definition of restricted $k$-set cover no existence.
– GOLD
Jun 2, 2017 at 4:45
• Can you explain yours with an example? Jun 2, 2017 at 15:14
• So it seems that when you're checking for membership in each $S_{i_j}$, you need to keep all $i_{p < j}$. For this reason, its not straightforward why it would be in $L$, let alone $NL$.. Cool problem though, it feels like one of these ones which would have the same parallel lower bound as sequential. Jun 3, 2017 at 7:31
• @TayfunPay Example: Given $U=[6]$, $S_1=\{2,3,4\}$, $S_2=\{4,5\}$, $S_3=\{1,5\}$, $S_4=\{3,4,5\}$,..,$k=3$ first step $S_1=\{2,3,4\}$ second step $S_1\cap S_2=\{4\}$ third step $S_1\cap S_2 \cap S_4=\{4\}$.
– GOLD
Jun 5, 2017 at 7:55