3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ [Check this out.][1] [1]: books.google.com/… $\endgroup$
    – Tayfun Pay
    Jun 2, 2017 at 2:44
  • $\begingroup$ @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. $\endgroup$
    – GOLD
    Jun 2, 2017 at 4:45
  • $\begingroup$ Can you explain yours with an example? $\endgroup$
    – Tayfun Pay
    Jun 2, 2017 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Samuel Schlesinger
    Jun 3, 2017 at 7:31
  • $\begingroup$ @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\}$. $\endgroup$
    – GOLD
    Jun 5, 2017 at 7:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy